CSE 421 Assignment #7
Autumn 2008

Due: Friday, November 21, 2008.

Reading Assignment: Kleinberg and Tardos Chapter 7 (sections 7.1, 7.2, 7.3, 7.5, 7.6, 7.11). Begin reading Kleinberg and Tardos 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 8, page 418.

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

  3. Kleinberg and Tardos, Chapter 7, Problem 23, pages 428-429.

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