Assignment 1: The Gale-Shapley Algorithm and Review of Big-O Notation
CSE 417: Algorithms and Computational Complexity
The University of Washington, Seattle, Winter 2013
The reading for this assignment is Chapters 1 and 2 of Algorithm Design by Kleinberg and Tardos. Do this assignment independently, without the use of online resources or collaboration.
Due Friday, January 18. Submit your answers to items 2-7 as hardcopy at the beginning of class.
 
  1. Survey (10 points). Complete the online background survey.
     
  2. Gale-Shapley Algorithm (22 points). Find stable matchings (or report any instabilities) for the following problem instance using these four different variations on the Gale-Shapley algorithm.
    • a. man-optimal
    • b. woman-optimal
    • c. proposing alternates between men and women, starting with a man. Proposing is by the first unengaged member of the gender whose turn it is to propose; orders are A, B, C, D, and W, X, Y, Z; that is, Art proposes before Bob, etc. Whenever an engagement is broken off or a proposal is rejected, however, proposing continues by the same gender.
    • d. same as in (c) except that the first proposer is a woman.
    The men are: Art, Bob, Cal, and Don.
    The women are: Wendy, Xanthippe, Yvonne, and Zoe.
    The preferences are: 
    
Art: Xanthippe, Zoe, Yvonne, Wendy
Bob: Wendy, Yvonne, Zoe, Xanthippe
Cal: Wendy, Xanthippe, Zoe, Yvonne
Don: Zoe, Wendy, Xanthippe, Yvonne

Wendy: Don, Cal, Bob, Art
Xanthippe: Cal, Bob, Art, Don
Yvonne: Don, Cal, Art, Bob
Zoe: Cal, Bob, Don, Art
    Express your solutions in the following form: 
        A-W, B-X, C-Y, D-Z
    Note that this matching is not a stable one, however, since (C-X) is an instability. Identify another instability in this matching (2 points). You may find it helpful to watch the demo at the website listed below. The "game" is also very instructive. 
    http://mathsite.math.berkeley.edu/smp/smp.html

     
  3. Properties of Stable Matchings 1 (8 points). In Kleinberg and Tardos, Chapter 1, Exercise 1. Either prove it to be true or prove it to be false (e.g., by giving a counterexample).
     
  4. Properties of Stable Matchings 2 (10 points). In Kleinberg and Tardos, Chapter 1, Exercise 2. Either prove it to be true or prove it to be false.
     
  5. 5-Minute Runtimes (30 points). Suppose you have the five running times given below (and assume they are exact). Suppose you have a computer that performs 1012 (i.e., 10 to the 12 power) operations per second, and that you will need to compute the answer to your problem in at most 5 minutes. For each algorithm, give the largest input size n for which you would be able to get the result within five minutes. 
    a.  n^2
b.  n^3
c.  n log n  ; (Assume the base of the logarithms here is 2.)
d.  2^n
e.  2^(2^n)

     
  6. Big O Hierarchies (10 points). In Kleinberg and Tardos, Chapter 2, Exercise 5.
     
  7. E-I-E-I-O (10 points). In Kleinberg and Tardos, Chapter 2, Exercise 7.
     
Updates and Corrections: Note that the phrase "(or report any instabilities)" was added to Problem 2 (January 8).