### CSC 421: Algorithm Design & Analysis Spring 2014 HW5: D&C vs. Dynamic

In the lectures, we considered two different solutions to the World Series puzzle. The divide & conquer solution utilized recursion to break the problem into simpler instances and combined solutions to those instances to solve the overall problem. The dynamic programming solution utilized a table of subproblem solutions that it filled in a bottom-up manner. Both solutions were based on a simple recurrence relation that defined how a problem solution could be built out of solutions to smaller problems.

For this assignment, you will consider a new game named Roller Derby that is being introduced at the CU Casino for the Probabilistically Challenged. In Roller Derby, a player puts down a stack of tokens, and the house matches that with an equal-sized stack. The player is able to select two numbers in the range 1-6, and the house does the same from the remaining numbers. Then the player repeatedly rolls a 6-sided die. If a roll matches one of the player's selected numbers, then the house loses a token from its stack and places it in the pot. If the roll matches one of the house's numbers, then the player loses a token to the pot. If the roll is matches one of the two unselected numbers, then both the player and the house lose a token to the pot. The game continues until either the player or the house completely runs out of tokens. At that point, all of the tokens in the pot go to the one with tokens remaining.

For example, suppose a player begins a game with a stack of 4 tokens and selects the numbers 1 and 6. The house selects 3 and 4. If the first roll is a 1, then the house loses a token, leaving it with only 3 (the player still has 4). If the next roll is a 2, both lose a token, leaving the house with 2 and the player with 3. If the next roll is a 6, then the house loses a token, leaving it with only 1 (the player still has 3). If a 5 is rolled next, then both lose a token, leaving the house with none and the player with 2. At that point, the player is declared the winner and gets all of the tokens. Note that if both run out of tokens on the same turn (i.e., both have 1 token remaining and an unselected number is rolled), then the house wins.

### Part 1: Divide & Conquer Solution

Create a class named `RollerDerby` that contains the following static method:

/** * Determines the probability that the player will win a game in progress. * (using a top-down, divide & conquer approach). * @param playerTokens the number of tokens currently held by the player * @param houseTokens the number of tokens currently held by the house * @return the probability (between 0.0 and 1.0) of the player winning the game */ public static double oddsTopDown(int playerTokens, int houseTokens)

1. If you call the `oddsTopDown` method repeatedly with the same inputs, will you always get the same answer? If so, explain why. If not, describe what random events contribute to the differing answers.
2. If a game is begun with only 1 token in each stack, what would you expect the probability of winning to be? Explain your reasoning, then verify your answer by calling the method.
3. As the number of initial tokens varies, does the probability of winning remain consistent, or does it change according to some pattern? Explain the pattern you see.
4. Is there a practical limit to the initial size of the token stack that your `oddsTopDown` can handle? In particular, if you want to know the probability of winning a game in which the player and house start with N tokens, how big of an N can your method handle before the delay is significant?

### Part 2: Dynamic Programming Solution

Add an additional method to your `RollerDerby` class named `oddsBottomUp`. This method should have the same parameters as `oddsTopDown` and should calculate the same value, only now using a dynamic programming approach. In particular, it should avoid duplicate calculations by building up a table of answers in a bottom-up fashion.

2. Is this version noticeably faster? If so, how large can the initial stack size get before the delay using `oddsBottomUp` is significant?