CS 6500 Project 2

July 10
due July 25

This project may be done in groups of size 3.  It may also 
be done in groups of size 4 if 2 group members do Prim and 2 group
members do Kruskal.  

Implement Prim's algorithm with binary heaps.  Test it on worst-case data and
random data (edge costs i.i.d. U[0,1]) to verify that is \theta(E log V) in 
the worst case and \theta (E+   V log^2 V) on average.  

Implement Kruskal's algorithm with bucket sort and disjoint sets (chapter 22).
What is the worst-case performance of your algorithms?  Test it on worst-case
data to partly verify your analysis.  Test your algorithm on
random data.  Verify that its average performance is 
nearly O(E) on random data.

Finally, compare the computational performance (not the theoretical performance)
 of the two algorithms. When is one faster than the other?  Can you see
why?  

Extra credit: find a way to speed up Prim's algorithm to make it O(E) on 
average for random data.  Implement and test your idea.  Talk to me first
so you don't waste effort.