Models of Computation - Mathematics 450 - Fall 2006

For HW #19

For a graph G, V(G) and E(G) denote, respectively, the set of all vertices and edges of G. Vertices are often labeled by numbers, and edges are often denoted by their endpoints. For example, if e is an edge whose endpoints are vertices 5 and 8, then e = (5,8) or {5,8}. A subset S of V(G) is said to be independent if no two vertices in S are adjacent.

Problems marked [Optional] are important and must be done, but turn them in only if you're not sure how to do them.

1. [Optional] See page 165 in Wilf for this problem:

   1. Give the answer to the Bin Packing problem when S = {1, 2, 3, 4, 5} and K = 7 and N = 3.
   2. Give the answer to the Bin Packing problem when S = {1, 2, 3, 4, 5} and K = 8 and N = 2.
   3. Give the answer to the Bin Packing problem when S = {1, 2, 3, 4, 5} and K = 7 and N = 2.

    
2. (The definition of the adjacency matrix can be found in Wilf, page 166.)

   1. Give the adjacency matrix of K₄, the complete graph on four vertices.
   2. Draw a graph whose adjacency matrix has rows: 0,1,0,0; 1,0,1,1; 0,1,0,0; 0,1,0,0.
   3. Is every square matrix of 0's and 1's the adjacency matrix of some graph? Prove your answer.

    

3. [Optional] What does an instance of a problem mean? Give an instance of TSP.
4. On page 168 (Wilf), line -12 ("negative 12" means 12 lines from the bottom), it says:
   "The extra multiplicative factor of log n will not alter ..."
   1. Why is it "multiplicative", not "additive"?
   2. Where does "log n" come from?
   3. Why does this extra factor not alter the polynomial versus nonpolynomial running time distinction?

    

5. Give the set of all 2x2 and 3x3 adjacency matrices in the "Graph 3-Coloring language" (see bottom of page 168 in Wilf).
6. Wilf, page 170, line 24: "It finally checks that for each edge e of G, it is true that ..."
   It is pretty clear that the two steps before this one take O(n) steps. What is the maximum number of steps this third step can take? Explain.
7. Wilf, page 170, line -4: "Any suggestions for a certificate?"
   I have a suggestion:
   List all possible tours, and next to each, write its total length. This can be done algorithmically. Creating this list may take very long, but that's not an issue here (why not?). This is my "certificate".
   Verifying the certificate is easy: just add up the relevant inter-city distances for each tour to check that the total given for each tour in the list is correct, and then check that none of these totals is less than K.
   Q: What's wrong with my "proof" that the problem "There is no tour of length less than K" is in NP?
    
8. 1. Give a polynomial-time algorithm for finding the smallest integer among n distinct integers. In your algorithm you may use the predicate "x < y" as one step.
   2. Give a polynomial-time algorithm for sorting n distinct integers into increasing order.