CSE 421 Assignment #4
Winter 2003
Due: Friday, Feb 7, 2003.
Reading Assignment: Read Chapter 4 of Kleinberg and Tardos.
Problems:
For all problems on this homework prove that your algorithm is correct
and analyze its worst-case running time.
- Kleinberg and Tardos, Section 3.6, Problem 13, page 97.
- Kleinberg and Tardos, Section 3.6, Problem 14, page 97.
- Kleinberg and Tardos, Section 4.4, Problem 1, page 115.
- Extra credit: Kleinberg and Tardos, Section 3.6, Problem 15, page 97.
- Extra credit: Feedback on the rest of Chapters 3 and 4 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.