CSE373 Data Structures Wi06, Homework 5

Programming problems due online Thursday, 3/2/06, at 11 pm.
Written problems due at the beginning of class, Friday, 3/3/06, 2:30 pm.
No late assignments will be accepted.

This assignment devleops a graph implementation so that we can perform more complicated graph algorithms in the following week.

The assignment has several files provided:

• AbstractGraph.java - Abstract (incomplete) implementation of the Graph interface.
• AdjListGraph.java - Implementation using an adjacency list. Fill in the remaining code.
• AdjMatrixGraph.java - Implementation using an adjacency matrix. Fill in the remaining code.
• Edge.java - Edge class. Fill in the opposite method.
• Graph.java - Graph interface.
• Vertex.java - Vertex class.

What to do - Coding Problems

As usual, your code should not only work properly, but it also should be high-quality. In particular:

• Write clean code - prefer simple and clear to complicated, unless there is a compelling reason, which should be clearly explained in comments. Avoid duplicate code or other situations where the same thing appears in more than one place. Use sensible names, indent clearly, and format your code so it blends cleanly with existing code.
• Use appropriate JavaDoc comments to specify all public classes, interfaces, methods, and any other features of your code that need documenting.

What to do - Written Problems

Answer these questions on a separate sheet of paper. We suggest you do these problems early as part of your preparation for the programming part of the assignment.

1. For each of the methods in the interface, say what their Big-Ohs are for each implementation (adjacency matrix and adjacency list). Explain why. Use terms such as the number of vertices, the number of edges, and the degree of a vertex.
2. Online social communities such as Facebook, Friendster, and MySpace have a graph-like structure. Using the vocabulary we learned in class, explain how the following statements could be posed as graph problems. Define what edges and vertices are.
   • Bob is one of Jen's friends.
   • Bob is Jen's friend, and Jen is Bob's friend.
   • Jack is reachable from clicking one of Bob's friends, then one of that friend's friends, so on.
   • Bob has 8 friends, 57 friends of friends, and 291 friends of friends of friends, totalling 356.
3. Write pseudocode for an algorithm to see if an undirected graph is bipartite (that is, if it is possible to color the graph in such a way that no two adjacent vertices share the same color).