CSE 421 Assignment #8
Autumn 2005

Due: Wednesday, November 23, 2005, 1:30 pm.

Reading Assignment: Kleinberg and Tardos Chapter 7.1-7.3, 7.5-7.6.

Problems: (see Grading Guidelines sheet before answering)

1. Give as good a bound as you can on the following recurrence, and prove your answer is correct:
   T(0,0) = 0;
   T(n,m) = T(j, m/3) + T(k-j, m/3) + T(n-k, m/3) + cnm for j < k < n.

2. Kleinberg and Tardos, Chapter 6, Problem 22, page 330-331 (yes, this was the E.C. problem on Assignment 7).

3. Kleinberg and Tardos, Chapter 7, Problem 1, pages 415.

4. Kleinberg and Tardos, Chapter 7, Problem 3, pages 415-416.

5. Kleinberg and Tardos, Chapter 7, Problem 5, page 416.

6. Extra credit: Kleinberg and Tardos, Chapter 6, Problem 23, pages 331.