CSC 421: Algorithm Design & Analysis
Spring 2015

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 competition in which two players repeatedly play a game that can end in a win, loss, or tie (e.g., chess, rock-paper-scissors, karaoke showdown). The players each begin with the same number of tokens. If a game results in a winner, then the loser forfeits one of his/her tokens. If the game results in a tie, then both players forfeit a token. The competition ends when one of the players runs out of tokens, and the other player is declared the winner (or it ends in a draw if both run out simultaneously).

For example, suppose Katherine challenges Michael to a lawn darts competition where each player starts with five tokens. It has been determined that Katherine's odds of winning a game are 0.50 and Michael's odds of winning are 0.30 (with a 0.20 chance of a tie). Thus, there is a 50% chance that she will win the first game (resulting in a token count of 5-4), a 30% chance that she will lose the first game (resulting in a token count of 4-5), and a 20% chance that they will tie (resulting in a token count of 4-4). The competition will continue until one or both players run out of tokens.

Part 1: Divide & Conquer Solution

Create a class named Competition whose constructor has two parameters: the probabilities of a player and his/her opponent winning a game, respectively. These probabilities should each be between 0.0 and 1.0, and should add up to a number less than or equal to 1.0. Your class should also have the following method:

/** * Determines the probability that the player will win a competition in progress * (using a top-down, divide & conquer approach). * @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 double oddsOfWinningTopDown(int tokens, int oppTokens)

Finally, create a driver program that allows the user to specify the winning probabilities and the initial number of tokens, and displays the odds of the first player winning the competition. Using your program, answer the following questions and provide experimental results to justify your answers.

  1. Suppose the two players are evenly matched and ties are not possible, i.e., the odds of each player winning a game are 0.50. Does the initial number of tokens affect the results of the competition? Is there a pattern to the players' odds as the initial number of tokens varies?
  2. Suppose the players are evenly matched, but there is a chance of a tie, e.g., the odds of each player winning a game are .40. Does the initial number of tokens affect the results of the competition? Is there a pattern to the players' odds as the initial number of tokens varies?
  3. How sensitive is the overall outcome to changes in the single game probability? For example, if the players' odds of winning a game are 0.55 and 0.45, would you expect player 1 to win the competition 55% of the time? Does the initial number of token affect your expectations?
  4. Is there a practical limit to how long of a game that your oddsOfWinningTopDown 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 Competition class named oddsOfWinningBottomUp. This method should have the same parameters as oddsOfWinningTopDown 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 long can the games be before the delay using oddsOfWinningBottomUp is significant?
  3. Suppose the players' odds of winning a game are 0.60 and 0.40. If player 1 starts with 20 tokens, how many should player 2 start with if we want the competition to be as fair as possible?
  4. Suppose the players' odds of winning a game are 0.60 and 0.30 (with the possibility of a tie). If player 1 starts with 20 tokens, how many should player 2 start with if we want the competition to be as fair as possible?