CSE 421 Assignment #1
Autumn 2006

Due: Wednesday, October 4, 2006, 1:30 pm.

Reading Assignment: Kleinberg and Tardos Chapters 1 and 2.

Problems: (see Grading Guidelines sheet before answering)

1. Kleinberg and Tardos, Chapter 1, Problem 1, page 22

2. Kleinberg and Tardos, Chapter 1, Problem 2, page 22

3. Kleinberg and Tardos, Chapter 1, Problem 5, page 22

4. Extra credit: Kleinberg and Tardos, Chapter 1, Problem 7, page 26 (This one is tricky - the problem is understanding the problem. It may be helpful to consider how to encode the example in Figure 1.8 as a stable matching problem.)