Homework Assignment 5

Graphs

15-211 Summer 2010

Due August 5th, 2010 at 11:59:59pm

For this assignment you will be implementing a general graph class and associated algorithms. This is the most extensive assignment. As before, you may work in pairs.

Objectives

Theory Questions: 15 points

In the file theory.pdf there are some short theory questions. Please answer the questions in this file and turn it in class.

Starter Code

Download the starter code for assignment (zip file). Once you finish implementation, FTP java files to /afs/andrew.cmu.edu/course/15/211/handin

What to Submit

You FTP the following java files

Do not submit anything else like zip files, folders, desktops, class files. Make sure you do not use packages in your java files as well. Failure to do so will result in a 20 point penalty.

The Graph Class: 15 points

The core of this assignment is the Graph class. The graphs we are dealing with are directed weighted graphs. Our graphs do not allow any self-loops, nor they allow multiple edges between vertices. There are many possibly ways of implementing this class Ideally, your implementation should be:

Of course, there are tradeoffs, and you should think about what representation will do best overall.

The Dijkstra algorithm: 15 points

Your first task, once your graph class is working well, is to implement Dijkstra's shortest-path algorithm. The algorithm should stop as soon as it has found the shortest path from the start vertex to the end vertex. Dijkstra's algorithm can fail on graphs with edges of negative weight, therefore implementation should throw an IllegalArgumentException in such cases.

The Graph class takes two generic types. V is a type for vertices -- you can choose any class you want in the vertices of your graphs. E is the type for edges that extends the Edge class.

Your implementation should run in O((|V|+|E|) log(|V|)) time. Note, you cannot use Java's Priority Queue for this assignment, however you can reuse it from your previous assignment. The PriorityQueue decreaseKey method must run in logarithmic time.

The Bellman-Ford algorithm: 15 points

Your implementation should give the same result as Dijkstra's algorithm on graphs with positive-weight edges. Furthernore, it should find a shortest path on graphs with negative-weight edges as long as there are no negative-weight cycles. You throw an IllegalArgumentException in the latter case.

Your implementation should run in O(|V|*|E|) time.

The Kruskal algorithm: 15 points

You are to implement Kruskal's minimum spanning tree algorithm. Your implementation should run in O(|V|+|E|*log|E|) time, To achieve this runtime, you should implement the Union-Find algorithm..

The Union-Find algorithm: 15 points

In your code, you are required to implement the union by rank heuristic. This heuristic is used when applying the union operation to two trees. You are also required to implement path compression. This heuristic means that when we perform a find operation on element x, we first find the root of the tree for x's equivalence class and then we set the parent of all nodes on the path from x to the root to be the root.

Coding Style: 10 points

Your assignment will be graded first by compiling and testing it. After that, we will read your code to determine whether appropriate data structures and algorithms were used, as well as judge the overall style of your code. Programs will be graded both on correctness as well as their ability to deal with so-called edge cases, like empty lists, lists with only one element, and so on. Points will be deducted for poor design decisions and un-commented, or un-readable code as determined by your TA.