COS 226 Programming Assignment #8

Checklist

Why doesn't my certificate of elimination look like the ones generated for the reference solution, or for the examples on the assignment page?  There may be more than one certificate of elimination for a given network.  If there is, it is okay to print out any one.

How do I compute the min cut?  Review the proof of the max-flow min-cut theorem.  It is constructive and tells you how to find a min cut from a max flow.  You will need to add a new interface method to MaxFlowSolver.java so that the client can access it.

Input, Output, and Testing

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

Reference solutions.   For reference, we provide executable code for our solution in Windows, Solaris, and OS X.  Note that the certificates of elimination provided by these programs may not exactly match yours since a given network may have more than one.

Submission and readme

Submit everything needed to compile your program (except for StdIn.java which we will supply).  Put your main program in BaseballEliminator.java.

Your program report should answer these questions.

Getting started

• Download the directory baseball.  This directory is mirrored on arizona at /u/cos226/pub/spring05/baseball. It contains a reference implementation, sample input files, and a max flow solver similar to the one described in the Sedgewick text.

• Your program shouldn't be too long, 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.