HW4 Prim's Algorithm Implementation

Due 3/13 before class starts

CS350

• Collaboration: You may work in groups of up to 3 students per group. Remember to clearly indicate the group members on your HW submission.
• Format: Preferably typeset in LaTeX but nearly handwritten is okay too, as a .pdf file.
• Submission: Your group submit your work in a single email to cs350pdx@gmail.com as well as all the group members.
• IMPORTANT: Provide an email subject line with the following pattern: HWx Section xxx - Full Name, Full Name, Full Name

The answers that you provide should clearly demonstrate that you understand the assignment and should provide enough information to clearly explain your solution to a peer.

---

Problem 1 (50 pts):

In a programming language of your choice, implement Prim's greedy algorithm for finding a minimum-spanning tree in a weighted undirected graph. You can find a discussion of Prim's algorithm as well as pseudocode in 9.1 of the textbook. While you're encouraged to research and explore ideas from the internet, you should develop your own implementation and not just copy-paste someone else's implementation.

Prim's algorithm constructs a minimum spanning tree through a sequence of expanding subtrees, by greedily attaching the minimum weight edge that's not in the tree.

You should test your implementation for correctness. You should also be able to parse and test it against the graph in the following weighted edge file City Pairs. You should output the distance between each pair of vertices as well as the cumulative and total distance of the resulting minimum-spanning trees.

You should submit the following:

1. The source code for your implementation

   • With instructions on how to build and run

2. A write up including the following points:

   • Briefly describe your development process.
   • What sources did you use to help you implement the algorithm?
   • What programming language did you choose and why?
   • What data structures did you use and why? How are you representing your graph?
   • Did you run into any difficulties with the implementation?
   • Example outputs from your testing as well as the results from the graph in city-pairs.txt file.

---

Extra Credit (20 pts):

Implement Kruskal's algorithm for greedily finding a minimum-spanning tree. This requires implementing a union-find (or disjoint set) abstract data structure to keep track of which vertices of a forest are in the same connected component. A discussion of Kruksal's algorithm as well as union-find is in 9.2 of your textbook. You can find more information about union-find at the following wikipage: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Same as above, you should test your implementation for correctness. You should also be able to parse and test it against the graph in the following weighted edge file City Pairs. You should output the distance between each pair of vertices as well as the cumulative and total distance of the resulting minimum-spanning trees.

You should submit the following:

1. The source code for your implementation

   • With instructions on how to build and run

2. A write up including the following points:

   • Briefly describe your development process.
   • What sources did you use to help you implement the algorithm?
   • What programming language did you choose and why?
   • What data structures did you use and why? How are you representing your graph?
   • Did you run into any difficulties with the implementation?
   • Example outputs from your testing as well as the results from the graph in city-pairs.txt file.