CSE 421 Assignment #1
Autumn 2007

Due: Friday, October 5, 2007.

Reading Assignment: Kleinberg and Tardos Chapters 1 and 2.

Problems: (see Grading Guidelines sheet before answering)

  1. Kleinberg and Tardos, Chapter 1, Problem 3, page 22-23.

  2. Kleinberg and Tardos, Chapter 1, Problem 4, pages 23-24.

  3. Kleinberg and Tardos, Chapter 1, Problem 7, pages 26-27
    (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, Chapter 1, Problem 8, pages 27-28.