CS 311 Algorithms and Complexity
 Spring 2007

Programming Project 3

For this project you are going to implement the algorithm you wrote for problem 12 from the text on page 112 (Written Assignment 3).  In particular, you are writing an analyzer that validates genealogical data.

Activities

Write a class called Contemporaries, which analyzes genealogy data to find generational inconsistencies as described in the written problem.  Your application should be run with the command

            java Contemporaries <filename>

where filename specifies the name of a file containing a directed genealogy graph.  Running the class should result in a message saying the file is consistent, or a message indicating that there is a problem.  You should try to give meaningful error messages where possible.

We will use a file format to represent the information.  Each row of the file consists of a single relationship.  There are two relationship types:

·        >  The person on the left died before the person on the right (e.g. Theseus>Romulus).

·        = The person on the left life overlapped the person on the right (e.g. Lycurgus=Romulus)

Use the following files to test your implementation. (I believe the files are correct.  Let me know if there are problems.) 

·        OK.txt – A graph with consistent data.

·        notOK.txt – A graph with inconsistent data.

Your solution should use the AdjacencyListDirectedGraph class that you built for the last assignment.

Project Report

Answer the following questions in a file called memo.doc.  Each individual must write their own memo.doc.  Explain your answers.

1.      What inconsistencies will your program identify?  Where does your program identify that there is an inconsistency, but does not offer specifics of the problem?

2.      If you worked in a pair:

a.       Describe your contribution to the project.

b.      Describe your partner’s contribution to the project.

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

·        Contemporaries.java

·        Any other java files you want us to consider

Assessment

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

Attribute

Advanced

Proficient

Needs Improvement

Maximum Pts

Behavior

Contemporaries

Correctly implements the algorithm and correctly identifies a number of inconsistencies.

Correctly implements the algorithm and correctly identifies some inconsistencies.

Inorrectly implements the algorithm

25

Design & Code

Design

Logical design.

A few design flaws present.

Many design flaws present.

10

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.

5

memo.txt

Question 1

Correct and clear explanation.

Correct and mostly clear explanation.

Incorrect analysis and/or unintelligible explanation.

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.

5

Total

50