Problem Set #3, CS 255, due April 9, 2007

Final version
 

  1. Exercise 34-3, (d), (e), and (f), p. 1019-20 of Cormen et al.

    In doing (e), you may assume the truth of the claim in (d). In doing (f), you may assume the truth of the claims in (d) and (e), and you may assume that an instance of 3-CNF-SAT has size Ω(m).

     

  2. As suggested by Exercise 16.2-2 of Cormen et al, a dynamic programming algorithm exists for the 0-1 version of the knapsack problem. Suppose we let n be the number of items, W be the capacity of the knapsack, and p be an n by W array where p(i,w) gives the optimal value for the knapsack subinstance consisting of the first i items of the original instance, and capacity w. Then the dynamic programming algorithm is based on the recurrence
    p(i,w) = 0 if i=0
    p(i-1,w) if i > 0 and w < wi
    max{p(i-1,w), vi + p(i-1,w-wi)} otherwise

    Show how the dynamic programming algorithm based on this recurrence would fill the array p for the 0-1 knapsack instance where the weight sequence (wi) = (6,3,2,5,4), the value sequence (vi) = (21,10,5,13,12), and W = 12. Do not sort or otherwise rearrange these input sequences; the algorithm will work fine without your doing so.

    Don't forget to state the optimal value and the set of items that need to be included in the knapsack to achieve the optimal value. You needn't use any particular algorithm to determine this set of included items.

     

  3. Trace the behavior of the last TSP approximation algorithm discussed in class (the one with 1.5 approximation ratio) on the planar graph with the following 10 vertices v0 - v9 from ℝ2: (4,2), (5,3), (4,4), (3,4), (2,3), (0,3), (1,2), (2,2), (2,1), (1,0).

    Assume that the graph is complete and undirected, and use 2-dimensional Euclidean distance for the cost of each edge. You needn't use any particular algorithm to find the minimum-cost spanning tree, or to find the minimum-cost matching.

    Do verify that your approximation is within the bound promised by the algorithm. The optimal cost is approximately 15.070.