Homework 8 (assigned February 28, due March 6)

Reading: CLRS chapter 35.

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. Exercise 35.1-2, page 1111.

2. Exercise 35.1-3, page 1111.

3. Exercise 35.1-5, page 1111.

4. Exercise 35.2-3, page 1117.

5. Exercise 35.2-4, page 1117.

6. Exercise 35.2-5, page 1117.

7. Exercise 35.3-2, page 1122.

8. Exercise 35.3-5, page 1122.

Problems (to be handed in):

1. Give an O(V + E) algorithm that finds an optimal vertex cover for a tree. Input is an undirected tree T = (V, E) in adjacency list format.
   • Describe your algorithm in pseudocode. (5 points)
   • Justify your algorithm's O(V + E) time complexity. (1 point)

2. Show that for any integer n that is a power of 2, there is an instance of the Set Cover problem with the following properties:
   1. There are n elements in the base set X.
   2. The optimal set cover uses just two sets.
   3. The greedy Set Cover algorithm picks at least log n sets.
   Thus the log n approximation ratio we derived in class is tight. (5 points)

3. Problem 35-3, page 1135. (9 points: 5 points for the algorithm (write pseudocode); 4 points for justification of the approximation ratio.)

4. Problem 35-4, page 1135. (25 points: part a, 2 points; part b (write pseudocode), 8 points; part c, 5 points; part d, 2 points; part e, 4 points; part f, 4 points.)

5. Problem 35-6, page 1137. (20 points: part a, 2 points; part b, 2 points; part c, 4 points; part d, 4 points; part e (write pseudocode), 8 points.)

6. Recall: a cut of an undirected graph G = (V, E) is a partition of V into two disjoint subsets S and V − S. An edge (u, v) crosses the cut (S, V − S) if one of its endpoints is in S and the other is in V − S. The MAX-CUT problem is the problem of finding a cut of an undirected connected graph G = (V, E) that maximizes the number of edges crossing the cut. Give an efficient deterministic approximation algorithm for this problem with an approximation ratio of 2. (Hint: your algorithm should guarantee that the number of edges crossing the cut is at least half the total number of edges.)
   • Describe your algorithm in pseudocode. (8 points)
   • Analyze the running time of your algorithm. (2 points)
   • Prove that your algorithm has an approximation ratio of 2. (5 points)