CSC 421: Algorithm Design & Analysis
Spring 2018

HW6: D&C vs. Dynamic

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

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:

BASE CASE: probOfWinNing((SERIES_LENGTH+1)/2, ?) = 1.0 BASE CASE: probOfWinning(?, (SERIES_LENGTH+1)/2) = 0.0 RECURSIVE CASE: probOfWinning(W, L) = PROB_OF_WINNING_A_GAME * probOfWinning(W+1, L) + PROB_OF_LOSING_A_GAME * probOfWinning(W, L+1) +

Part 1: Divide & Conquer Solution

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:

Enter the probability that your team will win any given game (0.0 - 1.0): 0.60 Enter the maximum series length (an odd number): 7 Their probability of winning the series is 0.71 Enter the probability that your team will win any given game (0.0 - 1.0): 0.50 Enter the maximum series length (an odd number): 5 Their probability of winning the series is 0.5 Enter the probability that your team will win any given game (0.0 - 1.0): -1 DONE

Test your code on a variety of data values and answer the following questions:

  1. If the teams are evenly matched (i.e., the game-winning probability is 0.5), should the probability of either team winning the series also be 0.5? Does the length of the series matter in that case? Explain your reasoning and justify your answer with experimental data.
  2. How sensitive is the overall outcome to changes in the single game probability? For example, if a team's probability of winning a game is 0.55, would you expect them to win the series 55% of the time? If the game-winning probability increases (say from 0.55 to 0.65), would you expect the change in the series-winning probability to be proportional? Explain your reasoning and justify your answer with experimental data.
  3. How sensitive is the overall outcome to changes in the length of the series? For example, if a team's probability of winning a game is 0.55, would you expect a longer series to increase or decrease their probability of winning the series? Explain your reasoning and justify your answer with experimental data.
  4. Is there a practical limit to how long of a series that your method can handle? In particular, if you want to know the probability of winning an N-game series, how big of an N can your method handle before the delay is significant?

Part 2: Dynamic Programming Solution

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:

  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 long can the series be before the delay using probOfWinningBU is significant?
  3. Suppose the IBL (Insane Baseball League) decided to have their championship decided by a summer-long 61-game series (i.e., the first team to 31 wins is the champion). What would be the probability of winning this series if a team's game-winning probability is 0.55? What about 0.65? What about 0.80?