CSPP 55005 Algorithms — Winter 2013
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
"Do" Exercises (not to be handed in):
Exercise 35.1-2, page 1111.
Exercise 35.1-3, page 1111.
Exercise 35.1-5, page 1111.
Exercise 35.2-3, page 1117.
Exercise 35.2-4, page 1117.
Exercise 35.2-5, page 1117.
Exercise 35.3-2, page 1122.
Exercise 35.3-5, page 1122.
Problems (to be handed in):
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)
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:
Thus the log n approximation ratio we derived in class is tight.
There are n elements in the base set X.
The optimal set cover uses just two sets.
The greedy Set Cover algorithm picks at least log n sets.
Problem 35-3, page 1135. (9 points: 5 points for the algorithm (write pseudocode);
4 points for justification of the approximation ratio.)
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.)
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.)
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)
Gerry Brady and Janos Simon
Thursday February 28 12:50:52 CST 2013