October 23, 2008

**Printed Name:**________________________________________

"On my honor, as an Aggie, I have neither given nor received unauthorized aid on this academic work. In particular, I certify that I have not received or given any assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment."

**Signature:**___________________________________________

- (1 pt) Consider Kruskal's MST algorithm that uses the disjoint sets data
structure to check for cycles.
What is its running time, as a function of |V| (number of nodes)
and |E| (number of edges)?

- (1 pt) Consider Prim's MST algorithm that uses a binary heap to
implement the priority queue.
What is its running time, as a function of |V| (number of nodes)
and |E| (number of edges)?

- (2 pts) Suppose you want to find the minimum spanning tree of
a complete graph (an edge exists between every pair of nodes).
Which of the two algorithms mentioned above is better, and
what is the running time?

- (1 pt) What is the key difference between Prim's MST algorithm and Dijkstra's SSSP algorithm?