CSC 421: Algorithm Design and Analysis
Spring 2018

HW3: Divide & Conquer Streaks

In 2017, 25-year old Scott Blumstein earned $8.1 million by winning the main event at the World Series of Poker. Despite this being his first World Series tournament, Blumstein was able to compete with older and more experienced opponents by first honing his skills playing thousands and thousands of online poker games.

You are to complete a program that will read in the winnings (and losses) of a poker player over an extended period of time. Since poker players want to highlight their successes, you are to identify the streak of consecutive games in which the player earned the most money and report the winnings for that streak.

For example, suppose a player competed in 10 games, with the following winnings/losses:

200 -150 -300 500 1000 -200 300 -800 100 -600 Over the course of the 10 games, the player lost a total of $50. However, if you consider the streak from game 4 to game 7, there was a period in which the player won $1600. While the $50 loss is the most accurate representation of the player's results, it is not hard to see that a player would prefer to tout the $1600 wining streak.

The Poker class contains a main method for reading in numbers from a file, representing a sequence of winnings/losses from games by a player. For example, poker10.txt contains the 10 outcomes from above. You are to complete two different static methods that calculate the maximum streak winnings or MSW, i.e., the largest amount won over a consecutive sequence of games.

mswBrute: This method should use a brute force approach to calculate the MSW. It should try every possible streak systematically, and determine which streak has the highest winnings total.

mswDivide: This method should calculate the same value, only using a divide-and-conquer approach. The basic algorithm is as follows:

  1. If the sequence consists of only one game, then the MSW is the amount won/lost in that game.
  2. Otherwise,
    1. Divide the sequence in half.
    2. Recursively calculate the MSW of the first half. Call this max1.
    3. Recursively calculate the MSW of the second half. Call this max2.
    4. Determine the MSW that crosses the two halves (by looping from the middle to the front and keeping track of the maximum sum, similarly looping from the middle to the end and keeping track of the maximum sum, and then adding the two maximum sums). Call this max3.
    5. Return the maximum of max1, max2, and max3.

After you have completed your implementations and tested them thoroughly, provide a Big-Oh analysis of each algorithm. That is, identify the Big-Oh performance of each along with an explanation of how you determined it. Large data files, poker1k.txt, poker2k.txt, poker4k.txt and poker8k.txt are provided for you (containing 1,000, 2,000, 4,000 and 8,000 numbers, respectively). Test your methods on these files, report the timings (using the StopWatch class), and analyze whether these timings support your Big-Oh classifications.