CSE 421: Introduction to Algorithms
Assignment #3
January 23, 2002
Due: Wednesday, January 30

Reading Assignment: Kleinberg and Tardos, chapter 3.

Problems

  1. Kleinberg and Tardos, page 87, problem 1.
  2. Kleinberg and Tardos, page 88, problem 3.
  3. Kleinberg and Tardos, page 89, problem 5.
  4. Extra Credit: Kleinberg and Tardos, page 91, problem 8.
  5. Extra Credit: Feedback on Sections 3.1-3.3 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.