### CSC 421: Algorithm Design & Analysis Spring 2019 HW6: 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.

In a related problem, consider a game in which two players start with the same number of tokens. Each round in the game (arm wrestling, staring contest, karaoke showdown, whatever) results in the loser forfeiting a token. The game continues until one of the players runs out of tokens, and the other player is declared the winner. If the probability of a particular player winning an individual round is fixed, then it should be possible to calculate the probability of that player winning an entire game.

For example, suppose Vicky and Grant are playing a game in which Vicky is acknowledged to be the better player (with a 0.60 probability of winning any given round). If both players are down to a single token, then the probability of Vicky winning is 0.60 (since she has a 0.60 probability of winning the round and a 0.40 probability of losing it). Alternatively, if Vicky has two remaining tokens and Grant has only one, then her probability of winning is even better. There is still a 0.60 probability that she will win the game on the next round. However, there is also a 0.24 chance that she will win it in two rounds (0.40 probability of losing the first round to get to one token each, then a 0.60 probability of winning the second round). Thus, the probability of Vicky winning the game is 0.60 + 0.24 = 0.84.

### Part 1: Divide & Conquer Solution

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

/** * Determines the probability that a player will win a game in progress * (using a top-down, divide & conquer approach). * @param winProb the probability of winning a single round (0 <= winProb <= 1) * @param tokens the number of tokens currently held by the player * @param oppTokens the number of tokens currently held by the opponent * @return the probability of winning the game */ public static double probTopDown(double winProb, int tokens, int oppTokens)

1. Suppose the two players are evenly matched, i.e., the probability of winning a single round is 0.50. If the players have the same number of tokens, what would you expect `probTopDown` to return?
2. How sensitive is the overall outcome to changes in the single round probability? For example, if the probability of winning a single round is 0.75 (and the players start with the same number of tokens), would you expect that player to win the game roughly 0.75 of the time?
3. Assuming the players are not evenly matched, does increasing or decreasing the initial number of tokens affect the probability of either player winning?
4. Is there a practical limit to how long of a game that your `probTopDown` can handle? In particular, if you want to know the probability of winning a game in which the players 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 `GameSim` class named `probBottomUp`. This method should have the same parameters as `probTopDown` 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 long can the games be before the delay using `probBottomUp` is significant?