CSE 421 Assignment #7
Autumn 2007
Due: Wednesday, November 28, 2007.
Reading Assignment: Finish reading Kleinberg and Tardos Chapter 7 (sections 7.1, 7.2, 7.3, 7.5, 7.6, 7.11) and begin reading Chapter 8.
Problems: Re-read the Grading Guidelines before answering (For all problems on this homework prove that your algorithm is correct and analyze its worst-case running time.)
- Kleinberg and Tardos, Chapter 7, Problem 3, pages 415-416.
- Kleinberg and Tardos, Chapter 7, Problem 5, page 416.
- Kleinberg and Tardos, Chapter 7, Problem 8, page 418.
- Kleinberg and Tardos, Chapter 7, Problem 13, pages 420-421.
- Kleinberg and Tardos, Chapter 7, Problem 14, page 421.
- Extra credit:
Kleinberg and Tardos, Chapter 7, Problem 19, page 425-426.
- Extra credit:
Kleinberg and Tardos, Chapter 7, Problem 34 (a), page 435-436.