CSE 421 Assignment #9
Winter 2009

Due: Friday, March 13, 2009, 1:30 pm. (Yes, the due date is Friday!)

Reading Assignment: Kleinberg and Tardos, 7.1-7.2, 7.5-7.7, 7.10, 8.1-8.4.

Problems: (see Grading Guidelines sheet before answering)

1. Chapter 7, Page 416, Problem 4.

2. Chapter 7, Page 418, Problem 8.

3. Chapter 7, Page 419, Problem 9.

4. Chapter 7, Page 420, Problem 13.

5. Chapter 8, Page 505, Problem 1.

6. Chapter 8, Page 506, Problem 5. (Note - show the problem is NP complete by giving a reduction from a problem shown to be NP complete in the text.)