Background

Fast forward to June 2003. You have graduated from UW with a degree in Computer Science, and have taken a job as a software developer at Roadhog Truck Lines, Inc. in Walla Walla, WA.

Upon reporting to work, you learn that your first assignment is to make sense out of Roadhog’s truck dispatching schedule, currently a confused mish-mash of hand-written pages and yellow sticky notes pasted to your boss’s computer screen. Your boss tells you, “On a given day, we could have trucks spread across the state from Aberdeen to Yakima. We need to dispatch any one of those trucks to its next stop by the shortest route possible. I took an Excel course last year, so I thought I might solve this problem myself using Excel. But I keep getting circular references, whatever the hell that means. Anyway, I figured we needed professional help.”

A few months ago, you learn, your boss hired a contract programmer named Lee T. Haxor to make sense of the mish-mash. Unfortunately, it appears that Haxor’s primary contributions to Roadhog have been to identify the Washington State Department of Transportation’s official Mileage Chart, and then to spend the rest of his time playing Doom with the Roadhog system programmers. Your hapless boss has begun to suspect that Haxor is not quite earning his $2,000 per day fee, and he is hoping that you might be able to bail him out. He tells you that he has terminated Haxor, effective at 5:00pm that day, and asks you to learn what you can from him before he leaves for good.

You knock on Haxor’s half-open door and find him leaning back in his chair, arms stretched out full-length, fingers blazing across the keyboard at ninety words a minute. He is apparently trying to hack his way into the eBay auction database from behind a Roadhog IP address, while he can still do so. “C’mon in,” he says. “You the new kid? I heard about you!” You introduce yourself and he responds, “Call me leet, kid. The ‘l’ is lower case.”

You learn from Haxor that, in addition to unearthing the invaluable Mileage Chart, he has written a program that imports the mileages into a more useable format (including simple and dense test cases). After that stellar effort, he seems to have given up working on Roadhog’s scheduling needs, and retreated to the relative safety of Doom. “Yeah, I looked at their scheduling thing, but I told that clown it’s a graph problem. NP-complete. No hope. He didn’t believe me. I guess that’s why he hired you. Good luck, kid.” You depart, feeling a mite confused.

On the way back to your office, however, a light bulb goes on. Isn’t the problem your boss described simply single-source shortest paths, with non-negative weights? If so, you should be able to solve it using Dijkstra’s Algorithm!

Dijkstra and Friends

You recall from your CSE 326 class that Dijkstra’s Algorithm requires a priority queue to keep track of graph vertices by minimum path distance as it runs. You also recall that, because path distances change as the algorithm runs, you will need a dictionary to efficiently access the vertices so that their key values can be updated. Finally, you decide to make a good first impression by writing clear, consistent code. You describe all this to your boss, who says, “I don’t know much about bikers or logarithms, but I can certainly help out with the dictionary,” and hands you the Webster’s from his bookshelf.

Your assignment

Your assignment is to solve Roadhog’s problem by implementing Dijkstra’s Algorithm, in stages:

	Deliverables	Credit (points)	Due date
Stage 1	Working priority queue. Unit tests for priority queue. Design document for entire project.	28 8 12	Wed, Nov 28
Stage 2	Working graph data structure. Unit tests for graph. Working Dijkstra’s Algorithm. Unit tests for Dijkstra’s Algorithm.	28 8 20 8	Fri, Dec 7
Review	Project Review with CSE 326 teaching team.	8	Dec 10-12
		120

As in previous projects, your efforts will be judged 70% on correctness of function, 30% on quality of code.

Partnering

Please do this project in 2-person teams. If you need help finding a partner, email cse326 or let us know.

Stage 1

Priority Queue

Your first step is to create a fully-functional priority queue which supports the IPriorityQueue interface. Your priority queue should use Comparator function objects to compare its key values (this provides callers with lots of flexibility as to what they can store in the queue).

You also need to supply unit tests for your priority queue, so that its functions can be verified separately from client code (see General Principles, below). We have supplied a very simple priority queue unit test, and some ideas for creating more comprehensive ones.

Dictionary

You can meet your dictionary requirement either by using the Webster’s Dictionary on your boss’s bookshelf, or by using some dictionary code left behind by Haxor. After reviewing Haxor’s dictionary code, you decide that it looks suspiciously like the clean, simple dictionary implemented by your TA in CSE 326, so you decide to go straight to the source.

Design document

Along with your stage 1 code, you need to hand in a simple, brief design document which describes your software design for the entire project. This document has a simple goal: a knowledgeable developer should be able to read your description and from it implement the code. The design document could include block diagrams, English descriptions, pseudocode or a combination. It should not regurgitate known art; for example, it should not describe Dijkstra’s Algorithm or a binary heap. Instead, it should describe how you propose to combine those or other pieces of known art into your working implementation of Dijkstra’s Algorithm.

This document could be no more than a single page and do complete justice to the goal. If it is more than two pages, you are probably over-doing it.

Stage 2

Graph

Your next step is to create a fully-functional graph which implements Dijkstra’s Algorithm. You will probably find it easier to first get the basic graph methods working, then implement Dijkstra last.

Again, you will need to supply unit tests for the basic graph operations, and for Dijkstra’s Algorithm.

General Principles

Unit Testing

Unit testing allows you to independently verify the function of a piece of code

You need to deliver unit tests for your priority queue in Stage 1, and for your graph data structure and Dijkstra’s Algorithm in Stage 2.

Sample Code and Style Guide

You also notice that Haxor has left behind some sample code and a coding style guide, but once again it looks suspiciously like the clean, elegant style guide written by your TA in CSE 326. You decide to go straight to the sources (sample code and a coding style guide).

Project Review

Finally, since your boss at Roadhog is clearly incapable of reviewing your efforts, you will need to review your code and your project as a whole with the CSE 326 teaching team. We will schedule some times during Dec 10-12 to enable this.

Extra credit

(3 points) Implement the random shuffle unit test for your priority queue.

(8 points) Re-implement your priority queue using a leftist heap in place of the binary heap.

(6 points) Re-implement your priority queue using a skew heap in place of the binary heap.

(8 points) Implement Kruskal’s Algorithm and use it to find a minimum spanning tree for the dense test graph.

(6 points) Implement Prim’s Algorithm and use it to find a minimum spanning tree for the dense test graph.

(5 points) Profile your implementation of Dijkstra’s Algorithm using gprof. Your part 2 turnin should include a short paragraph with the following:
- Your expected performance bottlenecks for your program
- How your expectations differed (or were the same) as the gprof results. Did you find anything unusual/unexpeceted?
- The biggest bottleneck for your program, and what you think may be the cause

(1 point) Where’s the pork ? Identify the source of our porcine friend’s image, and win a point of extra credit.

(15 points) To impress your boss even further, write a program that computes the shortest path passing through each vertex in the graph exactly once. For credit, your algorithm should run in no more than O(n⁴). Your writeup should include a formal proof of the running time. Hint: How can the algorithm for the "Travelling Salesman Problem", be applied to this problem?

(Nobel Prize) Prove P = NP, or P ¹ NP.

[1] You have nothing to lose but your (tire) chains.