CSE 421 Assignment #4
Autumn 2006

Due: Wednesday, October 25, 2006, 1:30 pm.

Reading Assignment: Kleinberg and Tardos Chapter 5 (Note: 4.8 and 4.9 will not be covered in class).

Problems: (see Grading Guidelines sheet before answering)

  1. Kleinberg and Tardos, Chapter 4, Problem 2, page 189

  2. Kleinberg and Tardos, Chapter 4, Problem 8, page 192

  3. Kleinberg and Tardos, Chapter 4, Problem 18, page 197-198

  4. Kleinberg and Tardos, Chapter 4, Problem 20, page 199-200

  5. Extra credit: Kleinberg and Tardos, Chapter 4, Problem 27, page 202-203
We had considered assigning Problem 29 as the extra credit problem - but decided it was too hard - if you are up for a challenge, you may do Problem 29 as the extra credit problem instead.