CSE 421 Assignment #7
Autumn 2007

Due: Wednesday, November 28, 2007.

Reading Assignment: Finish reading Kleinberg and Tardos Chapter 7 (sections 7.1, 7.2, 7.3, 7.5, 7.6, 7.11) and begin reading Chapter 8.

Problems: Re-read the Grading Guidelines before answering (For all problems on this homework prove that your algorithm is correct and analyze its worst-case running time.)

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

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

3. Kleinberg and Tardos, Chapter 7, Problem 8, page 418.

4. Kleinberg and Tardos, Chapter 7, Problem 13, pages 420-421.

5. Kleinberg and Tardos, Chapter 7, Problem 14, page 421.

6. Extra credit: Kleinberg and Tardos, Chapter 7, Problem 19, page 425-426.

7. Extra credit: Kleinberg and Tardos, Chapter 7, Problem 34 (a), page 435-436.