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. (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)?
   
   
   
   
2. (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)?
   
   
   
   
3. (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?
   
   
   
   
4. (1 pt) What is the key difference between Prim's MST algorithm and Dijkstra's SSSP algorithm?