**Assignment 05: Greedy Algorithms** *Due Thu Apr 8 11:00 PM Pacific Time* [Back to Algorithms](http://cs.pomona.edu/classes/cs140/) # Learning Goals - Implement an algorithm for solving the minimum spanning tree problem. - Learn how to analyze and develop greedy algorithms. # Overview This assignment includes two parts: 1. Answer the [question in this PDF](resources/greedy-algorithms.pdf). 2. Write a program for the problem described in section Minimum Spanning Trees (must be compatible with Python 3.8). You may work on this assignment alone or with a partner. Please send me a message on Slack if you want me to assign you to work with a random partner. Whether you work alone or with a partner, only one partner will submit both parts to [gradescope](https://www.gradescope.com/). Three key points for the hand written part: 1. you should either print the PDF and write your answers directly on the printed sheet, or add annotations to the PDF with Edge (Windows) or Preview (OSX) (using the correct format and spacing will help us grade), 2. ensure that the uploading partner adds the other partners after submission, and 3. **if you have any questions please ask them on [Slack](https://divisionii.slack.com/archives/G019H3HEXBK)**. # Example Execution I always like to start by showing you the end result. If you do not see an animation above this line (or if you see the animation but you don't see the progress bar), you will need to refresh the page (sometimes more than once). Or you can go directly to the player: https://asciinema.org/a/367833 **You can copy and past from the above animation!** # Minimum Spanning Trees Your program will accept two program arguments: (1) a filename and (2) a start vertex number. If you don't need it, your program can ignore the start vertex (i.e., if you are implementing Kruska'ls algorithm). Your program will output the cost of the minimum spanning tree. You should name your file `mst.py`. ## The input file Your programs will read a file the file given by a user. The file will include all of the information needed to create an **undirected** graph with edge costs. The file has the following format: ~~~ [n] [m] [v_i] [v_j] [c1] [v_a] [v_b] [c2] ~~~ Where the first line gives values for `n` and `m`, which are the number of vertices and number of edges, respectively. Each line after the first gives two vertex numbers (`v_i` and `v_j`; `v_a` and `v_b`) and then a cost for that edge (`cx`). Here is an example input file (it is also attached): ~~~ 5 7 1 2 2 1 4 6 2 3 3 2 4 8 2 5 5 3 5 7 4 5 9 ~~~  [Here are my test files](resources/tests.zip). ## Your program For full credit you must implement a $O(m lg n)$ version of Prim's algorithm or a $O(m lg m)$ version of Kruskal's algorithm. You will receive at most 80% credit for implementing the $O(mn)$ versions discussed in class. # Submitting Your Assignment You will submit your PDF assignment on [gradescope](https://gradescope.com/). **Only one partner should submit your PDF.** The submitter will add the other partner through the gradescope interface. You will also submit your code to gradescope. You will submit your Python file to gradescope. **Only one partner should submit your code.** The submitter will add the other partner through the gradescope interface. Please add your names in comments at the top of the file. To pass the autograder, your output must exactly match the expected output. You can use [text-compare](https://text-compare.com/) to compare your output to the expected output and that should give you an idea if you have a misspelled word or extra space (or if I do). I've enabled a leaderboard for the assignment. You do not need to worry about it affecting your grade. I just thought it looked like a cute feature. Feel free to give yourself (your group) any name you'd like for the leaderboard. Additional details for using gradescope can be found here: - [Submitting an Assignment](https://help.gradescope.com/article/ccbpppziu9-student-submit-work) - [Scanning Work on a Mobile Device](https://help.gradescope.com/article/0chl25eed3-student-scan-mobile-device) - [Adding Group Members](https://help.gradescope.com/article/m5qz2xsnjy-student-add-group-members) - [gradescope Student Help Center](https://help.gradescope.com/category/cyk4ij2dwi-student-workflow)