Description
Please see https://courses.cs.washington.edu/courses/cse421/20sp/grading.html for general guidelines about Homework problems.
Most of the problems only require one or two key ideas for their solution. It will help you a lot
to spell out these main ideas so that you can get most of the credit for a problem even if you err
on the finer details. Please justify all answers.
P1) Construct an instance of the stable matching problem with 4 men and 4 women and a stable
matching in which every man is matched to his least preferred woman.
P2) Prove that in the output of the Gale-Shapley algorithm (when men propose) at most one man
gets his last choice.
P3) Recall that the woman optimal matching is the output of the GS algorithm when women
propose to men. Prove that an instance of the stable matching problem has exactly one stable
matching if and only if the man optimal matching is equal to the woman optimal matching.
P4) Arrange the following in increasing order of asymptotic growth rate. For full credit it is enough
to just give the order.
(a) f1(n) = 23
√log n
(b) f2(n) = n3
2log log n
(c) f3(n) = n log n
(log log n)99
(d) f4(n) = n!
2
(e) f5(n) = n1.5/2
(f) f6(n) = nn/2
(g) f7(n) = 2log1/3 n
(h) f8(n) = 2log n
2log log n
(i) f9(n) = 2(2log n)
(j) f10(n) = �
22
�log n
P5) Gale and Shapley published their paper on the stable marriage problem in 1962; but a version
of their algorithm had already been in use for ten years by the National Resident Matching
Program, for the problem of assigning medical residents to hospitals.
Basically, the situation was the following. There were m hospitals, each with a certain number
of available positions for hiring residents. There were n medical students graduating in a
given year, each interested in joining one of the hospitals. Each hospital had a ranking of the
students in order of preference, and each student had a ranking of the hospitals in order of
1-1
preference. We will assume that there were more students graduating than there were slots
available in the m hospitals.
The interest, naturally, was in finding a way of assigning each student to at most one hospital,
in such a way that all available positions in all hospitals were filled. (Since we are assuming a
surplus of students, there would be some students who do not get assigned to any hospital.)
We say that an assignment of students to hospitals is stable if neither of the following situations
arises.
• First type of instability: There are students s and s′
, and a hospital h, so that s is
assigned to h, and s′ is assigned to no hospital, and h prefers s′ to s.
• Second type of instability: There are students s and s′
, and hospitals h and h′
, so
that
– s is assigned to h, and
– s′ is assigned to h′
, and
– h prefers s′ to s, and s′ prefers h to h′
.
So we basically have the stable marriage problem from class, except that (i) hospitals generally
want more than one resident, and (ii) there is a surplus of medical students.
Show that there is always a stable assignment of students to hospitals, and give an polynomialtime algorithm to find one.
P6) Extra Credit: Design an algorithm that outputs all stable matchings of a given instance with
n men and n women such that your algorithm runs in time polynomial in n and the number
of stable matchings of the input instance.
1-2
