COS 226 Programming Assignment Checklist: Baseball Elimination

Frequently Asked Questions

How efficient should my program be? You should be able to handle all of the test input files provided (say, in less than a minute). Do not worry about over-optimizing your program because the data sets that arise in real applications are tiny.

What should I return if there is more than one certificate of elimination? Return any such subset.

Must I output the teams in the same order as in the input file (as does the reference solution)? No, any order is fine.

Should certificateOfElimination() work even if isEliminated() has not been called by the client first? Absolutely. It is bad design (and a violation of the API) for the success of calling one method to depend on the client previously calling another method.

How do I compute the mincut? The inCut() method in takes a vertex as an argument and returns true if that vertex is on the s-side of the mincut.

How do I specify an infinite capacity for an edge? Use Double.POSITIVE_INFINITY.

What would cause to throw a runtime exception with the message "Edge does not satisfy capacity constraints: ..."? Did you create an edge with negative capacity?

My program runs much faster in practice than my theoretical analysis guarantees. Should I be concerned? No, there are a number of reasons why your program will perform better than your worst-case guarantee.


Input and testing. There are a number of sample input files in the directory baseball.

Testing.   For reference, the teams below are mathematically eliminated for nontrivial reasons. By nontrivial, we mean that the certificate of elimination requires two or more teams. If a team is trivially eliminated, it does not appear in the list below.

To verify that you are returning a valid certificate of elimination R, compute a(R) = (w(R) + g(R)) / |R|, where w(R) is the total number of wins of teams in R, g(R) is the total number of remaining games between teams in R, and |R| is the number of teams in R. Check that a(R) is greater than the maximum number of games the eliminated team can win

Possible Progress Steps

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

Your program shouldn't be too long—ours is less than 200 lines. If things get complicated, take a step back and re-think your approach.

Enrichment links