CSE 421 Assignment #6
Winter 2003

Due: Monday, March 3, 2003.

Reading Assignment: Read Chapter 6.1-6.5,6.7 of Kleinberg and Tardos.

Problems: For all problems on this homework prove that your algorithm is correct and analyze its worst-case running time.

1. Kleinberg and Tardos, Section 5.9, Problem 10, pages 169-170.

2. Kleinberg and Tardos, Section 5.9, Problem 20, pages 174-5.

3. Kleinberg and Tardos, Section 5.9, Problem 23, pages 177-8.

4. Extra credit: Kleinberg and Tardos, Section 5.9, Problem 15, page 172.

5. Extra credit: Feedback on Chapters 1 to 6 of Kleinberg and Tardos. This should be sent in e-mail to the address cse421-textbook@cs. Your message should contain your name prominently displayed at the start as well as the number of the chapter for which you are providing comments. If you have more than one comment, your comments should be laid out in some form of numbered or bulleted list.