CSE 421 Assignment #4
Winter 2005

Due: Friday, February 4, 2005.

Reading Assignment: Kleinberg and Tardos Chapter 5

Problems: For all problems on this homework prove that your algorithm is correct and analyze its worst-case running time.

1. Kleinberg and Tardos, Section 4.9, Problem 11, pages 149-150.

2. Kleinberg and Tardos, Section 5.10, Problem 1, page 212.

3. Kleinberg and Tardos, Section 5.10, Problem 2, page 213.

4. Extra credit: Kleinberg and Tardos, Section 4.9, Problem 18, page 154.