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

Reading Assignment: Kleinberg and Tardos, Sections 6.1-6.7

Problems

  1. Kleinberg and Tardos, page 155, problem 18.

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

  3. Kleinberg and Tardos, page 204, problem 3.

  4. Extra Credit: Kleinberg and Tardos, page 155, problem 7.

  5. Extra Credit: Feedback on chapter 5 and Sections 6.1-6.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 22 Feb 2002, 12:42.