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:

Once you have tested your method thoroughly, answer the following questions and provide experimental results to justify your answers.

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.

Answer the following questions and provide experimental results to justify your answers:

1. Does this new method return the same answers as the previous one? How would you go about testing this?
2. Is this version noticeably faster? If so, how large can the initial stack size get before the delay using oddsBottomUp is significant?
3. Revisit the question from above: 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.