CS 252: Algorithms

Problem Set #2: ?

The definitions of O and Ω

1. Prove that 2sqrt(log n) = O(n1/2).
2. Prove that n is not Ω(n2).
3. Let T(n) = the running time of linear search on an array of n items. Find f(n) and g(n) such that T(n) = Ω(f(n)) and T(n) = O(g(n)), and argue that your choices are as tight as possible.

Stable matching

4. Do Problem 1 on page 22 of your textbook.
5. Do Problem 3 on pages 22-23 of your textbook.

6. On page 5 of your textbook, the authors describe an example that has two different stable matchings. One of the matchings has very happy men, and the other has very happy women. Later (pages 10-11), the authors discuss the fact that the Gale-Shapely Algorithm as stated on page 6 always yields the stable matching that makes the collection of men as happy as possible given the preference lists. This "male-optimal" version of the algorithm becomes "female-optimal" if you swap the roles of the men and the women in the algorithm.

   Define partner_rankM(P) to be the preference rank that person P gives to his/her partner in matching M. Further, define the total happiness of a matching M to be the sum over all people P of partner_rankM(P). For example, the matching described on the bottom of page 4 and the top of page 5 has a total happiness of 6:

   partner_rankM(w) = 1
   partner_rankM(m) = 1
   partner_rankM(w') = 2
   partner_rankM(m') = 2

   Your jobs for this exercise are:

   1. Construct an example that has at least three stable matchings, at least two of which have different total happiness.
   2. Does Gale-Shapley find the stable matching with the best total happiness?
   3. Are there situations when an unstable matching has a better total happiness than a stable matching?
   4. Discuss whether total happiness is a good measure to use when choosing between stable matchings.