CSE 421 Assignment #5
Autumn 2007

Due: Friday, November 2, 2007.

Reading Assignment: Kleinberg and Tardos Chapter 6

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 6, Problem 3, pages 314-315.

  2. Kleinberg and Tardos, Chapter 6, Problem 5, pages 316-317.

  3. Kleinberg and Tardos, Chapter 6, Problem 6, pages 317-318.

  4. Extra Credit Kleinberg and Tardos, Chapter 6, Problem 4, pages 315-316.