In lecture, we studied the World Series Puzzle that determined the amount that needed to be bet on the first game of an N-game series in order to come out ahead or behind by exactly $1000. We identified the appropriate recursive relation and implemented it using a top-down, divide-and-conquer approach and also a bottom-up, dynamic programming approach.
For this assignment, you will solve a related problem: Given the likelihood of a team winning a single game and the length of the series, determine the probability of that team winning the series. For example, consider a series where one team (call them the Cubs) is 50% better than the other (call them the Cardinals). This implies that the Cubs' probability of winning a game is 0.60 vs. 0.40 for the Cardinals. In a one-game series, the probability that the Cubs would win is obviously 0.60. In a three-game series, the probability of the Cubs winning the series is actually 0.648 (there is a 0.6 * 0.6 = 0.36 probability of W-W, a 0.6 * 0.4 * 0.6 = 0.144 probability of W-L-W, and a 0.4 * 0.6 * 0.6 = 0.144 probability of L-W-W).
At any point in the series (assuming W wins and L losses so far), the team's winning probability for the series can be calculated using the following recursive relation:
Define a SeriesProb
class that contains a static method named probOfWinningTD
. This method should implement the above divide & conquer solution using top-down recursion. You should also have a driver class which allows you to repeatedly enter the game probability and the series length, and which displays the team's probability of winning the series. It should terminate when a negative value is entered for the probability. For example:
Test your code on a variety of data values and answer the following questions:
The potential drawback of a top-down implementation of divide & conquer is redundancy. If there is significant overlap between the recursive cases, the redundancy can grow exponentially, leading to drastic decreases in performance as the problem size grows.
Add a method named probOfWinningBU
which utilizes the same recursive relation but in a bottom-up fashion. Note that each recursive call has parameters for the number of wins and losses by your team. Thus, you should be able to create a table where the rows correspond to the number of wins and the columns correspond to the number of losses. That is, table[W][L] would store the probability of your team wining given that the series score is W-L. When the table is filled, the probability of your team winning at the start of the series should be at table[0][0].
Test your code on a variety of data values and answer the following questions:
probOfWinningBU
is significant?