CSE 421 Assignment #3
Winter 2009

Due: Wednesday, January 28, 2009, 1:30 pm.

Reading Assignment: Kleinberg and Tardos, 4.1-4.5, 4.7.

Problems: (see Grading Guidelines sheet before answering)

1. Chapter 4, Page 189, Problem 3.

2. Chapter 4, Page 190, Problem 5. Justify that your algorithm is correct.

3. Chapter 4, Page 191, Problem 6. Justify that your algorithm is correct.

4. Chapter 4, Page 194, Problem 13. Justify that your algorithm is correct.

5. Extra credit: Chapter 4, Page 197, Problem 17.