CSE 421 Assignment #8
Winter 2005

Due: Friday, March 11, 2005.

Reading Assignment: Finish reading Kleinberg and Tardos Chapter 8

Problems: For all problems on this homework if you are proving NP-completeness, give a full argument that shows that your reduction is correct and runs efficiently and make sure to prove that your problem is in NP also. If you are giving an algorithm, prove that your algorithm is correct and show that it runs efficiently.

  1. Kleinberg and Tardos, Section 8.9, Problem 5, page 407.

  2. Kleinberg and Tardos, Section 8.9, Problem 18, page 415.

  3. Kleinberg and Tardos, Section 8.9, Problem 20, page 416.

  4. Extra credit: Kleinberg and Tardos, Section 7.13, Problem 25, page 344-5.