CSE 421 Assignment #7
Winter 2005

Due: Friday, March 4, 2005.

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

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 7.13, Problem 3, page 330.

2. Kleinberg and Tardos, Section 7.13, Problem 5, page 331.

3. Kleinberg and Tardos, Section 7.13, Problem 14, page 336.

4. Kleinberg and Tardos, Section 7.13, Problem 8, page 333.

5. Extra credit: Kleinberg and Tardos, Section 7.13, Problem 40, page 357.