**Assignment 7: Complexity Classification** *Due Thu Dec 9 11:00 PM Pacific Time* [Back to Algorithms](http://cs.pomona.edu/classes/cs140/) # Learning Goals - Perform reductions. - Learn the characteristics of P, NP, NP-Complete, and NP-Hard problems. # Grading This assignment will be graded as pass/no-pass by a TA. To pass the assignment, you must 1. Complete every question in the PDF and submit your answers to gradescope. 2. Complete the programming component and submit your answers to gradescope. 3. Schedule a time to meet with a TA (see section Important Dates for deadlines). 4. Walk the TA through your answers. 5. The TA will then either - mark your assignment as 100% on gradescope, or - inform you that you have some corrections to make. 6. If corrections are needed, then you will need to complete them and then schedule a new time to meet with the TA. If you have concerns about the grading walk-through, you can meet with me after you've first met with a TA. # Walk-Through Guidelines - Walk-through should take no more than 20 minutes. You should be well prepared to walk a TA through your answers. - You may not make any significant corrections during the walk-through. You should plan on making corrections afterward and scheduling a new walk-through time. Mistakes are expected--nobody is perfect. - We will use the Google Sheet found on Slack to schedule your walk-through. This helps TAs manage their time and balance the grading load. - You must be prepared to explain your answers and justify your assumptions. TAs do not need to lead you to the correct answer during a walk-through--this is best left to a mentor session. # Important Dates - You should start this assignment Dec 2 - Submit your work prior to end of day Dec 9 - You must meet with a TA for grading prior to end of day Dec 10 + **It is a good idea to complete the assignment as early as possible** + **You must book a time to meet with a TA** - You should complete corrections by end of day Dec 10 # Overview This assignment includes two parts: 1. Answer the [question in this PDF](resources/complexity-classification.pdf). 2. Write a program for the problem described in section TSP Problem (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/450308 **You can copy and past from the above animation!** # TSP Problem For the coding portion of this assignment, you will implement the [Bellman-Held-Karp](https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm) algorithm for computing the shortest tour--solving the Traveling Salesperson Problem. To help out with this assignment, I am providing the following: - a set of [test files](resources/test_files.zip) - a [completed implementation of Bellman-Held-Karp](resources/tsp-example.py) (we're near the end of the semester...) The file you submit should be named `tsp.py`. I recommend tackling this problem as follows: 1. Grabbing the file-handling code from the completed example above. 2. Converting the following pseudocode into Python 3. Referring to my implementation if you get stuck ~~~text linenumbers FUNCTION BellmanHeldKarp(G) n = G.vertices.length # Compute all pairwise Euclidean distances between vertices dists = ComputeDistances(G) # Create and initialize a two-dimensional cost matrix # n : final vertex # 2^n : different sets of vertices (a powerset) costs = Matrix(n, 2^n) # Let's use 0 as the start vertex FOR v IN [1 ..< n] costs(v, {0, v}) = dists(0, v) # Compute paths for all possible subsets of vertices other_vertices = G.vertices - {0} FOR size IN [2 ..<= n] FOR subset IN PowerSet(other_vertices, size) FOR next IN subset min_cost = INFINITY state = subset - {next} FOR end IN state new_cost = costs(end, state) + dists(end, next) IF new_cost < min_cost min_cost = new_cost costs(next, subset + {0}) = min_cost # Grab the cheapest tour min_tour_cost = INFINITY FOR end IN [1 ..< n] tour_cost = costs(end, G.vertices) + dists(end, 0) IF tour_cost < min_tour_cost min_tour_cost = tour_cost # Compute the tour by back tracking through costs min_tour = ComputeTour(G, costs, dists) RETURN min_tour_cost, min_tour ~~~ The set of test files includes an example with 20 locations. This one is not tested by the autograder, but you should try to run your program with it as the input. # 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)