CSE 421 Assignment #1
Winter 2005

Due: Friday, January 14, 2005.

Reading Assignment: Kleinberg and Tardos Chapters 1 and 2.

Problems: (see Grading Guidelines sheet before answering)

1. Kleinberg and Tardos, Section 1.3, Problem 2, page 19

2. Kleinberg and Tardos, Section 1.3, Problem 4, pages 20-21

3. Kleinberg and Tardos, Section 1.3, Problem 8, pages 24 (see figure page 25)
   (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.3, Problem 3, pages 19-20.