CS 560, HOMEWORK 1 (DUE: SUNDAY SEPTEMBER 15, 11:59 PM)
INSTRUCTOR: HOA VU
Each question is worth 20 points. The extra credit question is worth 10 points.
When you are asked to design an algorithm, do the following: a) describe the algorithm, b) explain (or more rigorously prove) why it is correct, and c) provide the running time.
Unless specified otherwise, the problems are from the textbook by Jeff Erickson that we use.
(1) Question 1:
• Show that if f(n) = O(f′(n)) and g(n) = O(g′(n)) then f(n) + g(n) =
O(f′(n) + g′(n)).
• Use induction to prove that ni=0 i2i = 2 + (n − 1)2n+1.
• Solve T (n) = T (n − 1) + n2 using the recurrence tree method. In particular,
what is big-O of T(n).
• Solve T (n) = 4T (n − 1) + 99 using the recurrence tree method.
(2) Question 2: Problem 6 (page 49): Solve B,E,H using master theorem, and Problem 7 (page 49).
(3) Question 3: Problem 13 (page 51): Provide an O(n log n) time algorithm.
(4) Question 4: Problem 37 (page 64).
(5) Question 5: Problem 21, part a (page 55).
(6) Extra credit: Problem 26 (page 59): Hint, prove by induction that such tiling
always exists (for n = 1, 2, . . .).
1