CS 311 Algorithms and Complexity
Spring 2007

Programming Project 1

One use of graphs is to model networks, such as computer networks. One issue in network design is minimizing the number of hops that messages have to travel. In this program, you will implement algorithms to calculate two measures of the distance between nodes in a connected graph G:

· Diameter – the maximum length of a shortest path between any pair of vertices in G.

· Average Distance – the average length of a shortest path between distinct vertices in G.

Both of these properties can be calculated using breadth-first search, since breadth-first search starting at vertex v finds a shortest path from v to every vertex in G (since G is connected).

Activities

Download the net.datastructures 4.0 package from http://net3.datastructures.net/. This package contains a graph implementation called AdjacencyListGraph. Write a class called GraphAnalyzer that has a static method:

· public static void diameterReport( net.datasructures.Graph g ) – calculates and writes to stdout the diameter and average distance of graph g.

The file movies.txt should be used to test your implementation. Each row of the file contains the title and some actors from a movie. You can convert this file to a graph by having a vertex for each movie and each actor. An edge represents the relationship that the actor acted in the movie. Write a main method for the GraphAnalyzer class that reads the movies.txt file, creates the associated AdjacencyListGraph object, and runs the diameterReport method. Pay particular attention to the efficiency of your main method.

Project Report

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

1. What is the running time of the diameterReport method? Explain.

2. What is the running time of the main method? Explain your choice of data structures used in this method.

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

· GraphAnalyzer.java

· Any other java files you want me to consider

Assessment

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

Attribute	Advanced	Proficient	Needs Improvement	Maximum Pts
Behavior
diameterReport	Correctly implements the algorithms and successfully calculates both values.	Mostly correctly implements the algorithms and successfully calculates at least one of the values.	A number of flaws or incorrectly implemented algorithm	15
main	A correct and efficient implementation.	A correct, but less efficient implementation.	An incorrect or no implementation.	10
Design & Code
Design	Logical design.	A few design flaws present.	Many design flaws present.	3
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
Question 1	Correct and clear explanation.	Correct and mostly clear explanation.	Incorrect analysis and/or unintelligible explanation.	5
Question 2	Correct and clear explanation.	Correct and mostly clear explanation.	Incorrect analysis and/or unintelligible explanation.	10
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.	4
Total				50