CS180 Homework 1

CS180 Homework 1

1. (15 pt) In the class we showed that the number of iterations (number of proposals) in the Gale-Shapley
algorithm is upper bounded by ≤ n
2
for n men and n women, since each man can only make ≤ n proposals.
However, we haven’t shown a lower bound on number of iterations. To show the lower bound is also in
the order of n
2
, please give a way to construct the preference lists for n men and n women such that the
Gale-Shapley algorithm will run for Θ(n
2
) iterations. (For simplicity, you can assume that the algorithm
always chooses the unmatched man with the smallest index at each iteration).
2. (20 pt) Gale and Shapley published their paper on the Stable Matching 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 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
0
, and a hospital h, so that
– s is assigned to h,and
– s
0
is assigned to no hospital, and
– h prefers s
0
to s.
• Second type of instability: There are students s and s
0
, and hospitals h and h
0
, so that
– s is assigned to h,and
– s
0
is assigned to h
0
, and
– h prefers s
0
to s, and
– s
0 prefers h to h
0
.
So we basically have the Stable Matching Problem, 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 algorithm to find one.
3. (20 pt) The Stable Matching Problem, as discussed in the text, assumes that all men and women have a
fully ordered list of preferences. In this problem we will consider a version of the problem in which men
and women can be indifferent between certain options. As before we have a set M of n men and a set W
of n women. Assume each man and each woman ranks the members of the opposite gender, but now we
allow ties in the ranking. For example (with n = 4), a woman could say that m1
is ranked in first place;
second place is a tie between m2 and m3
(she has no preference between them); and m4
is in last place. We
will say that w prefers m to m0
if m is ranked higher than m0 on her preference list (they are not tied).
With indifferences in the rankings, there could be two natural notions for stability. And for each, we can
ask about the existence of stable matchings, as follows.
(a) A strong instability in a perfect matching S consists of a man m and a woman w, such that each of
m and w prefers the other to their partner in S. Does there always exist a perfect matching with no
strong instability? Either give an example of a set of men and women with preference lists for which
every perfect matching has a strong instability; or give an algorithm that is guaranteed to find a perfect
matching with no strong instability.
(b) A weak instability in a perfect matching S consists of a man m and a woman w, such that their partners
in S are w
0
and m0
, respectively, and one of the following holds:
– m prefers wto w
0
, and w either prefers m to m0 or is indifferent between these two choices; or
– w prefers m to m0
, and m either prefers w to w
0 or is indifferent between these two choices.
In other words, the pairing between m and w is either preferred by both, or preferred by one while
the other is indifferent. Does there always exist a perfect matching with no weak instability? Either
give an example of a set of men and women with preference lists for which every perfect matching has
a weak instability; or give an algorithm that is guaranteed to find a perfect matching with no weak
instability.
4. (10 pt) Take the following list of functions and arrange them in ascending order of growth rate. That is, if
function g(n) immediately follows function f (n) in your list, then it should be the case that f (n) is O(g(n)).
• f1
(n) = n
4
log n
• f2
(n) = p
2n
• f3
(n) = n
2
/2
• f4
(n) = 2
3log n
• f5
(n) = n(log n)
100
• f6
(n) = 2
log n−loglog n
5. (20 pt) You’re doing some stress-testing on various models of glass jars to determine the height from which
they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as
follows. You have a ladder with n rungs, and you want to find the highest rung from which you can drop a
copy of the jar and not have it break. We call this the highest safe rung.
It might be natural to try binary search: drop a jar from the middle rung, see if it breaks, and then recursively
try from rung n/4 or 3n/4 depending on the outcome. But this has the drawback that you could break a
lot of jars in finding the answer.
If your primary goal were to conserve jars, on the other hand, you could try the following strategy. Start
by dropping a jar from the first rung, then the second rung, and so forth, climbing one higher each time
until the jar breaks. In this way, you only need a single jar – at the moment it breaks, you have the correct
answer – but you may have to drop it n times (rather than log n as in the binary search solution). So here
is the trade-off: it seems you can perform fewer drops if you’re willing to break more jars. To understand
better how this tradeoff works at a quantitative level, let’s consider how to run this experiment given a fixed
“budget” of k ≥ 1 jars. In other words, you have to determine the correct answer – the highest safe rung –
and can use at most k jars in doing so.
(a) Suppose you are given a budget of k = 2 jars. Describe a strategy for finding the highest safe rung that
requires you to drop a jar at most f (n) times, for some function f (n) that grows slower than linearly. (In
other words, it should be the case that limn→∞ f (n)/n = 0.)
(b) Now suppose you have a budget of k > 2 jars, for some given k. Describe a strategy for finding the
highest safe rung using at most k jars. If fk
(n) denotes the number of times you need to drop a jar according
to your strategy, then the functions f1
, f2
, f3
, . . . should have the property that each grows asymptotically
slower than the previous one: limn→∞ fk
(n)/fk−1
(n) = 0 for each k.
6. (15 pt) Given K sorted linked lists, each one contains n numbers in the ascending order. Give an algorithm
to merge these K lists into a single sorted list. Your algorithm should run in O(nK log K) time.
Æ Homework assignments are due on the exact time indicated. Please submit your homework using the
Gradescope system. Email attachments or other electronic delivery methods are not acceptable. To learn
how to use Gradescope, you can:
– 1. Watch the one-minute video with complete instructions from here:
https://www.youtube.com/watch?v=-wemznvGPfg
– 2. Follow the instructions to generate a PDF scan of the assignments:
http://gradescope-static-assets.s3-us-west-2.amazonaws.com/help/submitting_
hw_guide.pdf
– 3. Make sure you start each problem on a new page.
Æ We recommend to use LATEX, LYX or other word processing software for submitting the homework. This is
not a requirement but it helps us to grade the homework and give feedback. For grading, we will take into
account both the correctness and the clarity. Your answer are supposed to be in a simple and understandable
manner. Sloppy answers are expected to receiver fewer points.
Æ Unless specified, you should justify your algorithm with proof of correctness and time complexity.