CS 311 Algorithms and Complexity
Spring 2007

Programming Project 2

For this project you are to implement and test a class that represents a directed graph.

Activities

There are two main activities for this project:

DirectedGraph

The net.datastructures package does not have a directed graph class. Your mission is to write the class AdjacencyListDirectedGraph that implements the DirectedGraph interface. This will require some thought.

Testing

The Design and develop a test suite to test the methods of your class. It is good practice to develop your testers before developing the code. Use JUnit to implement your testers. It is up to you to determine what constitute a good set of test cases, but each method should be thoroughly tested.

Project Report

In addition to your earlier prediction, answer the following questions in a file called memo.doc. Each individual must write their own memo.doc. Explain your answers.

1. Write a report explaining your test cases and how they test the methods of your class. Explain how your set of testers covers all methods and handles important cases.

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.doc

· AdjacencyListDirectedGraph.java

· Your JUnit testers

· 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
AdjacencyListDirectedGraph	Correctly implements all the methods of the interface.	Mostly correctly implements the methods of the interface.	A number of flaws or incorrectly implemented methods.	15
Testers	Thoroughly tests all methods.	Tests all methods..	Does not test all methods	15
Design & Code
Design	Logical design.	A few design flaws present.	Many design flaws present.	5
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