CS 311 Algorithms and Complexity
 Spring 2007

Programming Project 6

Introduction

In this project we will implement an example of an application of maximum flow.  

Activities

Section 7.12 in the text describes the Baseball Elimination problem, which analyzes the standings in a sports league and determines which teams are eliminated and which teams can still finish in first place. 

In this assignment you are to write a program called BaseballEliminator that reads in a sports league and prints out a list of all of the teams that are mathematically eliminated.  For each team, give a convincing reason why of the form described above.  For example, on the input file input4.txt,

    4
    Atlanta       83 71  8  0 1 6 1
    Philadelphia  80 79  3  1 0 0 2
    New_York      78 78  6  6 0 0 0
    Montreal      77 82  3  1 2 0 0

your program should output something like:

    Philadelphia is eliminated.
    They can win at most 80 + 3 = 83 games.
    Atlanta and New York have won a total of 161 games.
    They play each other 6 times.
    So on average, each of the teams wins 167/2 = 83.5 games.

    Montreal is eliminated.
    They can win at most 77 + 3 = 80 games.
    Atlanta has won a total of 83 games.
    They play each other 0 times.
    So on average, each of the teams in this group wins 83/1 = 83 games.

Assume that no games end in a tie (as is the case in Major League Baseball).  Also assume that there are no rainouts, i.e., every scheduled game is played.  Ignore wildcard possibilities, i.e., when a team can make the playoffs without finishing first in its division. 

Do not worry about over optimizing your program because the data sets that come from real applications are quite small.

File Format

The input file has the following format:

The first row indicates how many teams are in the league.  There is then one row for each team in the league.  The columns in each row are:

Directed Graph

You do not need to implement a directed graph class.  You can use the DirectedGraph interface and the AdjacencyListDirectedGraph class.

memo.doc

In your memo.doc:

1.      Demonstrate a test case for your program.  Turnin a file (test.txt) that is in the above format.  Demonstrate that your program works on this test case by explaining what teams are and are not eliminated and why.

2.      Write a brief report that describes the design of your program.

Turn in

By the due date and time, zip and email me a directory that contains any files you want me to consider.  This directory should have in it:

·                    memo.txt

·                    tst.txt

·                    BaseballEliminator.java

·                    Any other java files we will need to run your program.

Assessment

We will use the following rubric to assess your work on this project:

Attribute

Advanced

Proficient

Needs Improvement

Maximum Pts

Behavior

BaseballEliminator

Prints out all certificates correctly. 

Works mostly correctly.

Incorrect or no implementation.

 30

Design & Code

Code style

Uses good code style.  Code is mostly self-documenting.  Javadoc comments for each class and method.

Mostly correct with some comments.

Mostly not correct.  Poor code style.

3

memo.txt

Test Case

A test case that demonstrates the algorithm.  A clear and accurate description.

A test case that demonstrates the algorithm.  Mostly clear and accurate description.

A trivial or incorrect test case.  Unclear or inaccurate description.

10

Design description

Clear and accurate description.

Mostly clear and accurate description.

Unclear or inaccurate description.

5

Grammar and style

Well written. No obvious grammar or punctuation errors. A pleasure to read.

A few grammatical errors such as punctuation or spelling, although most errors do not interfere with the overall message or the substance of the text.

May grammatical errors including punctuation, spelling or usage problems.

2

Total

50