CS180 Homework 1 Solution

    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 n2 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 n2, please give a way to construct the preference lists for n men and n women such that the Gale-Shapley algorithm will run for (n2) 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 s0, and a hospital h, so that

– s is assigned to h,and

– s0 is assigned to no hospital, and

– h prefers s0 to s.
Second type of instability: There are students s and s0, and hospitals h and h0, so that
– s is assigned to h,and

– s0 is assigned to h0, and

– h prefers s0 to s, and
– s0 prefers h to h0.

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 w0 and m0 , respectively, and one of the following holds:
– m prefers wto w0, 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 w0 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) = logn4n

p

f2(n) = 2n f3(n) = n2=2

f4(n) = 23 log n

f5(n) = n(log n)100
f6(n) = 2log n  log log 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!1 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!1 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.