### CSC 421: Algorithm Design & Analysis Spring 2016 HW6: D&C vs. Dynamic

Note: late submissions will NOT be accepted for this final assignment.

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 Rollorama that is being introduced at the CU Casino for the Probabilistically Challenged. In Rollorama, a player puts down a stack of tokens, and the house matches that with an equal-sized stack. Then the player repeatedly rolls a pair of 6-sided dice. If the dice total is between 3 and 6, then the house loses a token from its stack and places it in the pot. If the dice total is between 8 and 11, then the player loses a token to the pot. If the dice total is 2, 7, or 12, 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 3 tokens, which is matched by the house. If the first roll is a 3, then the house loses a token, leaving it with only 2 (the player still has 3). If the next roll is a 7, both lose a token, leaving the house with 1 and the player with 2. If the next roll is a 10, then the player loses a token, leaving him/her with only 1 (the house still has 1). If a 5 is rolled next, then the house loses its last token. 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 a 2, 7 or 12 is rolled), then the house wins.

### Part 1: Divide & Conquer Solution

Create a class named `Rollorama` 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 `Rollorama` 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?