CSE 421 Assignment #1
Autumn 2012

Due: Friday, October 5, 2012.

Reading Assignment: Kleinberg and Tardos Chapters 1 and 2.

Problems: (see the Grading Guidelines before answering)

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

  2. Kleinberg and Tardos, Chapter 1, Problem 5, pages 24-25.

  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?)

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

    2. Kleinberg and Tardos, Chapter 2, Problem 4, page 67-68.

  5. Extra credit: Kleinberg and Tardos, Chapter 2, Problem 8, part (a), page 69-70. What is the asymptotic rate of growth of f(n) as a function of n in your solution? What are f(15) and f(16) using your solution?

  6. Extra credit: In the previous problem, determine the best possible solution and prove that nobody can do better.