Homework 9 (assigned March 3, due March 9)

Reading: CLRS chapters 34 and 35; Algorithms by Dasgupta, Papadimitriou, & Vazirani (DPV), chapter 8.

Written assignment : Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in.

"Do" Exercises (not to be handed in):

1. DPV Exercise 8.10, parts d, e, f, and g, page 266. Online page 279.

2. CLRS Exercise 34.5-2, page 1100.
   2nd edition, page 1017.

3. CLRS Exercise 34.5-3, page 1101.
   2nd edition, page 1017.

4. CLRS Exercise 35.1-2, page 1111.
   2nd edition, page 1027.

5. CLRS Exercise 35.1-5, page 1111. (See CLRS section 34.5.1 for Clique.)
   2nd edition, page 1027.

Your solutions for this homework set should be short and well-justified.
For problems which require you to write an algorithm, describe your algorithm in pseudocode, analyze its running time, and argue for its correctness. Your argument should be precise, i.e., rigorous enough to be converted to a formal argument if required.

1. DPV Exercise 8.4, parts a–c, page 264. Online page 278. (part a, 2 points; parts b and c, 4 points each)
   The Clique problem is presented in CLRS section 34.5.1.

2. CLRS Problem 34-1, parts c and d, page 1102. Write pseudocode. (8 points for each part)
   2nd edition, page 1018.

3. CLRS Problem 34-3, parts d–f, page 1103. (5 points for each part)
   2nd edition, page 1019.

4. CLRS Exercise 35.1-3, page 1111. Explain your answer. (6 points)
   2nd edition, page 1027.

5. CLRS Exercise 35.1-4, page 1111. Write pseudocode. (8 points)
   2nd edition, page 1027.

6. Given a set of positive integers A = {a₁, …, a_n} and a positive integer t, a subset S ⊆ A is called feasible if the sum of the numbers in S does not exceed t :
         ∑_{ai ∈ S} a_i ≤ t.
   The sum of the numbers in S is called the total sum of S.
   Goal: Select a feasible subset S of A whose total sum is as large as possible.
   Example: If A = {8, 2, 4} and t = 11, then the optimal solution is the subset S = {8,2}.
   1. An algorithm for this problem follows.
      01 S := ∅
      02 total := 0
      03 for i = 1 to n
      04      if total + a_i ≤ t then
      05         S := S ∪ {a_i}
      06         total := total + a_i
      Give an input for which the total sum of the set S returned by this algorithm is less than half the total sum of some other feasible subset of A. (5 points)
   2. Give a polynomial-time approximation algorithm for this problem with the following guarantee: it returns a feasible set S ⊆ A whose total sum is at least half as large as the maximum total sum of any feasible set S′ ⊆ A. Your algorithm should have a running time of O(n lg n). (It can be done in O(n) time.) Write pseudocode. Justify the approximation guarantee and justify the running time of your algorithm. (10 points)
   3. Could you solve this problem in O(nt) time using dynamic programming? Would your algorithm be polynomial? Explain. (2 points)

   ---

   Gerry Brady and Janos Simon
   Thursday March 3 14:44:09 CST 2011