CS 180 Homework 1 Solution

CS 180 Homework 1

Problem 1. Decide whether the following statement is true or false.
If it is true, give a short explanation.
If it is false, give a counterexample.
In every instance of the Stable Matching Problem, there is a stable matching containing a pair (m, w)
such that one of them is ranked first on the preference list of the other and the other is ranked either
first or second on the preference list of the first one.
Problem 2. Take the following functions and arrange them in ascending order of growth rate.
log2
2
n
log102n
log2n
3
log2
2
nn
log2
2
n+ 2n
log10 (10n)
alog10
2
n + blog10n + c
log2
2 (n + 2n)
Problem 3. Men, women and yupi live on the planet Alphaomega. Their family pattern is a triple that
consists of a man, a woman and a yupi. Three sets are given: M includes n men, W includes n women
and Y includes n yupi. A matching is a set H of ordered triples of the form (m, w, y) with the property
that each member of M, each member of W and each member of Y appears in at most one triple from
H. A matching H is called perfect if each member of M, each member of W and each member of Y
appears exactly in one triple from H.
Assume that each man ranks all women and all yupi, each woman ranks all men and all yupi, and
each yupi ranks all women and all men.
Two triples (m, w, y) and (m’, w’, y’) form an instability in a matching H if one of the following
conditions is true:
(1) m prefers w’ to w and w’ prefers m to m’
(2) m prefers y’ to y and y’ prefers m to m’
(3) y prefers w’ to w and w’ prefers y to y’
A matching H is called stable if it does not have instabilities.
Decide whether the following statement is true or false.
There is an algorithms that solves the Stable Matching Problem for every instance of this
problem.
If it is true, design an algorithm for building a stable perfect matching. Note that when you design
an algorithm, you have to prove that it solves the necessary problem
If it is false, give a counterexample.