1. Answer the following questions about the the Floyd-Warshall algorithm:

(a) (10 points) The algorithm currently computes n + 1 matrices D(0), D(1), ..., D(n) . Modify the algorithm so that it computes a single matrix D. Explain why when the algorithm terminates, D = D(n) holds.

(b) (10 points) Modify the algorithm you obtained in the previous question so that it computes the predecessor n n matrix .

2. (10 points) We know that the question of whether P = NP is unsolved. Lets assume that at some point in the future someone finds an algorithm for SAT that runs in (n ^5 ) time. We know this would imply that P = NP, but does it imply that all problems in NP are O(n^5 )? Why or why not?

3. (10 points) Restate as decision problems the following problems, each of which we have studied earlier in this course. (Note, these are not necessarily NP-complete; even non-NP-complete problems can be cast as decision problems!)

(a) Sort an array.

(b) Find the minimum value in an array of numbers.

(c) Given an unweighted graph G, find the longest simple path (no node can be visited more than once) in G.

4. (10 points) The hitting set problem is defined as follows: Given a collection C of subsets of a finite set S and a positive integer K |S|, is there a subset S 0 S with |S 0 | k such that S 0 contains at least one element from each subset of S in C? Prove that the hitting set problem is in NP. (It is also NP-complete - relatively easy to prove by reduction from the vertex cover problem, but well leave the NP-hardness proofs to the next homework.)

5. (10 points) Prove that the problem in Question 3c is in NP.

6. (10 points) Formulate the decision problem (called HAM-PATH) for the following problem: Given a graph G, find a simple path that visits every node in G.

7. (10 points) Prove that HAM-PATH is in NP.