CSE373 Data Structures Wi07, Homework 6
Due online Thursday,
3/1/07, at 11 pm.
No late assignments will be accepted.
This assignment devleops a graph implementation that we will use for more
complex graph algorithms in the final assignment, next week.
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.
- Although there is no formal requirement for how you should test your code,
you do need to verify that it works properly. JUnit tests are one good way
to do this.
I. Graph Representations
The assignment has several files provided:
Fill in the remaining code for AdjListGraph.java, and
Edge.java. Your code should be efficient and must have the minimal big-Oh
possible for the given implementation.
II. Priority Queue
Starter files for this part of the assignment are also provided:
Implement the methods in HeapPriorityQueue.java to create a priority queue
using a binary heap. Notice that this version of the queue contains a method
that can be used to change the priority of an object that is already in the
queue. You can use a sequential search to locate the item to be adjusted. Once
you've changed the priority of an item in the queue, you need to move it to
the proper place in the heap (i.e., reestablish the heap property). Other,
faster
implementations
of
a
priority
queue
with changable priorities exist, but this will be sufficient for our purposes.