CSE 421 Assignment #1
Winter 2003

Due: Friday, January 17, 2003.

Reading Assignment: Kleinberg and Tardos Chapter 1.

Problems: (see Grading Guidelines sheet before answering)

1. Kleinberg and Tardos, Section 1.5, Problem 1, page 28

2. Kleinberg and Tardos, Section 1.5, Problem 3, pages 29-30

3. Kleinberg and Tardos, Section 1.5, Problem 7, pages 32-33
   (HINT: Try to set up a stable matching problem that will solve this problem. How should the preferences be determined? Why will that work?)

4. Extra credit: Kleinberg and Tardos, Section 1.5, Problem 5, pages 30-31.

5. Extra credit: Feedback on chapter 1 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.