Assignment 7: Complexity Classification

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. Meet with your TA during your learning community sessions. I prefer both partners to be present during the walk-through, but you can each meet with the TA separately if needed.
  4. Walk the TA through your answers. Do not expect to make corrections during the walk-through.
  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 conduct a new walk-through with a TA.

If you have concerns about the grading walk-through, you can meet with me after you’ve first met with a TA.

Overview

This assignment includes two parts:

  1. Answer the question in this PDF.
  2. Write a program for the problem described in the TSP Problem section (must be compatible with Python 3.8).

You may work on this assignment alone or with a partner (I much prefer you to work 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 a both parts to gradescope.

Three key points:

  1. you should either print the PDF and write your answers directly on the printed sheet, or add annotations to the PDF with, for example, 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.

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 algorithm for computing the shortest tour–solving the Traveling Salesperson Problem.

To help out with this assignment, I am providing the following:

The file you submit should be named tsp.py. I recommend tackling this problem as follows:

  1. Grabbing the input-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. Only one partner should submit your PDF. The submitter will add the other partner through the gradescope interface.

To pass the autograder, your output must exactly match the expected output. Your program output should be similar to the example execution above, and the autograder on gradescope will show you the correct output if yours is not formatted properly. You can use text-compare 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).

Additional details for using gradescope can be found here: