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.

  1. Kleinberg and Tardos, Section 3.6, Problem 13, page 97.

  2. Kleinberg and Tardos, Section 3.6, Problem 14, page 97.

  3. Kleinberg and Tardos, Section 4.4, Problem 1, page 115.

  4. Extra credit: Kleinberg and Tardos, Section 3.6, Problem 15, page 97.

  5. 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.