COS 226 Programming Assignment Checklist: Baseball Elimination

What do I use to indicate a capacity of infinity for an edge? Use Double.POSITIVE_INFINITY.

What should I print out if there is more than one certificate of elimination? Choose any one subset.

How do I compute the min cut? The code is in FordFulkerson.java but review the explanation in the book starting on page 892 to understand the Ford-Fulkerson algorithm and to understand an st-cut. It is constructive and tells you how to find a min cut from a max flow.

When I try to run FordFulkerson.java why am I getting the following message: "Edge does not satisfy capacity constraints: ..."? If a team is eliminated for a trivial reason w[x] + r[x] < w[i], constructing the flow network will create an edge with negative capacity. Instead make this a special case.

Should certificateOfElimination() work even if isEliminated() has not been called first? Yes, each method should not make assumptions about the order in which methods are called or how how many times any one method is called. In general, it is bad API design to only be able to call one method if another has been previously called.

Should checkSolution() use the FlowNetwork or FordFulkerson objects that I created in other parts of the program? No.

Input, Output, and Testing

Input and output. Here are a number of sample input files.

Testing.  

The best way to keep testing to a minimum is to spend plenty of time on design.

Use FlowNetwork.toString() to check that your graph is correct.

Once your code is written, be sure to test with as much input as possible. For example, a minimum of testing for checkSolution() would be a case that returns true and one that returns false. But a more complete amount of testing would include more test cases.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

• Download the directory baseball. It contains sample input files, and the readme.

• First draw the FlowNetwork graph that you want to construct and calculate by hand the min cut before you write any code. In your code, use FordFulkerson methods, value() and inCut(). After you have written the code to construct the FlowNetwork, print it out and make sure that it matches what you intended it to be.

• The API contains the public methods that you will implement. For modularity, you will want to add some private methods of your own such as but not limited to
  • a method to create a FlowNetwork, and
  • a method to calculate the sum of all games left.

  Your program shouldn't be too long (~200 lines), so if things get complicated, take a step back and re-think things.

Enrichment links

• A group of researchers at Berkeley maintain a website where you can view the baseball elimination numbers as the season unfolds.