CSE 421 Assignment #5
Autumn 2006

Due: Friday, November 3, 2006, 1:30 pm.

Midterm, Friday, November 3. Midterm will cover material from text/lecture through the end of chapter 5.

Reading Assignment: Kleinberg and Tardos Chapter 5.

Problems: (see Grading Guidelines sheet before answering)

1. The Blum-Floyd-Pratt-Rivest-Tarjan Algorithm satisfies the following recurrence: T(n) < cn for n < 50, and T(n) < T(n/5) + T(3n/4) + cn for n >= 50. Show that T(n) <= dn for some d.

2. Give upper bounds for T(n) in each of the following examples. You may assume T(n) is constant for n <= 2.
   1. T(n) = 5T(n/2) + n
   2. T(n) = 9T(n/3) + n³
   3. T(n) = 3T(n/7) + n^1/2
   4. T(n) = T(sqrt(n)) + 1

3. Solve the following recurrence: T(n) = T(n/2)* T(n/2); T(1) = 2;

4. Kleinberg and Tardos, Chapter 5, Problem 2, Page 246.

5. Kleinberg and Tardos, Chapter 5, Problem 3, Page 246-247.

6. Extra credit: Kleinberg and Tardos, Chapter 5, Problem 5, Page 248.