CSPP 55005 Algorithms — Winter 2011
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):
-
DPV Exercise 8.10, parts d, e, f, and g, page 266.
Online page 279.
-
CLRS Exercise 34.5-2, page 1100.
2nd edition, page 1017.
-
CLRS Exercise 34.5-3, page 1101.
2nd edition, page 1017.
-
CLRS Exercise 35.1-2, page 1111.
2nd edition, page 1027.
-
CLRS Exercise 35.1-5, page 1111. (See CLRS section 34.5.1 for Clique.)
2nd edition, page 1027.
Problems (to be handed in):
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.
-
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.
-
CLRS Problem 34-1, parts c and d, page 1102. Write pseudocode.
(8 points for each part)
2nd edition, page 1018.
-
CLRS Problem 34-3, parts d–f, page 1103.
(5 points for each part)
2nd edition, page 1019.
-
CLRS Exercise 35.1-3, page 1111. Explain your answer. (6 points)
2nd edition, page 1027.
-
CLRS Exercise 35.1-4, page 1111. Write pseudocode. (8 points)
2nd edition, page 1027.
-
Given a set of positive integers A = {a1, …,
an} 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
ai ≤ 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}.
-
An algorithm for this problem follows.
-
01 S := ∅
02 total := 0
03 for i = 1 to n
04
if total + ai ≤ t
then
05
S := S ∪
{ai}
06
total := total +
ai
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)
-
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)
-
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