Exam 4: Graphs

Distributed: Friday, December 8, 2000
Due: 5 p.m., Friday, December 15, 2000
Those taking the free extension may not have their exams graded before the end of the semester.

This page may be found online at http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2000F/Exams/exam.04.html.

• Preliminaries
• Problems
  • Problem 1: Documenting Graphs
  • Problem 2: A Node-based Implementation
  • Problem 3: Shortest Path
  • Problem 4: Analysis

Preliminaries

There are four problems. Each problem is worth twenty-five points. For convenience, the problems are divided into sections. The point value associated with a problem does not necessarily correspond to the complexity of the problem or the time required to solve the problem. If you write down the amount of time you spend on each question, I'll give you three points of extra credit.

This examination is open book, open notes, open mind, open computer, open Web. Feel free to use all reasonable resources available to you. As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately.

This is a take-home examination. It is likely to take you about five to ten hours, depending on how well you've learned topics and how fast your work. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date. No late exams will be accepted.

You must include the following statement on the cover sheet of the examination. Please sign and date the statement. Note that the statement must be true; if you are unable to sign the statement, please talk to me at your earliest convenience. Note also that ``inappropriate assistance'' is assistance from (or to) anyone other than myself or our teaching assistant.

I have neither given nor received inappropriate assistance on this examination. I am not aware of any other students who have given or received inappropriate assistance on this examinatino.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say ``This is among the hardest exams I have ever taken. If you don't start it early, you'll have no chance of finishing the exam.'' You may also summarize these policies.

Answer all of your questions electronically and turn them in electronically and in hardcopy. That is, you must write all of your answers on the computer and print them out. You should also email me a copy of your exam (a plain text file, please) with a subject of ``CSC152 Exam 4''. Put your answers in the same order that the problems appear in.

I will give partial credit for partially correct answers. You ensure the best possible grade for yourself by emphasizing your answer and including a clear set of work that you used to derive the answer.

I may not be available at the time you take the exam. If you feel that a question is badly worded or impossible to answer, note the problem yo u have observed and attempt to reword the question in such a way that it is answerable. If it's a reasonable hour (before 10 p.m. and after 8 a.m.), feel free to try to call me in the office (269-4410) or at home (236-7445).

I will also reserve time at the start of classes next week to discuss any general questions you have on the exam.

Problems

Problem 1: Documenting Graphs

In our discussion of graphs, we decided the following methods would be useful:

• add(Object label) --- add a ``node'' labeled by the given object.
• addEdge(Object source, Object destination, double weight) -- add a directed edge from the node labeled by source to the node labeled by destination with the specified weight.
• delete(Object label) -- delete the node with the given label.
• deleteEdge(Object source, Object destination) -- delete the edge between source and destination.
• Object[] successors(Object label) -- get labels of all the nodes, n, for which there is an edge from the node with the given label to n.
• Object[] predecessors(Object label) -- get labels of all nodes, n, for which there is an edge from n to the node with the given label.
• int getWeight(Object source, Object destination) -- get the weight of an edge.
• Object[] getLabels() -- get all the labels in the graph.
• ??? getEdges() -- get all the edges in the graph.
• int numNodes() -- determine how many nodes are in the graph.
• int numEdges() -- determine how many edges are in the graph.

Turn this rough specification into a Java interface in which you specify the 6 Ps as well as any appropriate exceptions. Note that you will have to decide upon an appropriate return value for getEdges.

Problem 2: A Node-based Implementation

As I mentioned in class, one technique for implementing graphs involves building explicit Node objects for each node in the graph. A Node might contain a label and a collection of edges to neighboring nodes.

a. Write the Node class and any related classes.

b. Write a corresponding Graph wrapper class.

c. Explain how to implement getWeight in time dependent primarily on the number of neighbors of a node. (If there are no neighbors, it's okay if your implementation takes a fixed amount of time.) You should assume that we're still using the Node-based implementation.

d. Explain how to implement getPredecessors efficiently.

e. Sketch an implementation of delete.

Problem 3: Shortest Path

Express Dijkstra's shortest path algorithm in terms of these operations. You need not write working Java code (after all, you don't necessarily have a working implementation of these graphs or of priority queues), but it should be close enough that it convinces me that you could get it working with the appropriate utility classes and some mroe time.

Problem 4: Analysis

a. Make a chart of the running time of each basic graph operation for each of the three primary graph implementations (nodes, edge list, grid).

b. What is the running time of Dijkstra's algorithm in each implementation?