CSE 421: Introduction to Algorithms
Assignment #5
February 6, 2002
Due: Wednesday, February 20

Reading Assignment: Kleinberg and Tardos, chapter 5.

Problems

  1. Kleinberg and Tardos, page 109, problem 1.

  2. Kleinberg and Tardos, page 109, problem 2.

  3. Kleinberg and Tardos, page 145, problem 2.

  4. Kleinberg and Tardos, page 150, problem 9.

  5. Extra Credit: Kleinberg and Tardos, page 148, problem 6.

  6. Extra Credit: Kleinberg and Tardos, page 157, problem 20.

  7. Extra Credit: Feedback on Sections 4.2-4.3 and chapter 5 in book. Please submit this by email to both Erik and Anna.

For all problems on this homework, prove that your algorithm is correct, and analyse the worst-case complexity of your algorithm.



File translated from TEX by TTH, version 3.04.
On 7 Feb 2002, 17:30.