Description
1. (10 pt) Decide whether you think the following statement is true or false. If it is true, give a short explanation. If it is false, give a counterexample:
True or false? Consider an instance of the stable matching problem in which there exists a man m and a woman
w such that m is ranked first on the preference list of w and w is ranked first on the preference list of m. Then
in every stable matching S for this instance, the pair (m, w) belongs to S.
2. Let m1
, m2 be two of the men and w1
, w2 be two of the women in an instance of the Stable Matching Problem
with n men and n women. Assume m1
, m2
, w1
, w2
’s preference lists are:
m1
’s preference: w1 > w2 > . . .
m2
’s preference: w2 > w1 > . . .
w1
’s preference: m2 > m1 > . . .
w2
’s preference: m1 > m2 > . . .
So, we only know the favorite and the second favorite of each of these four persons.
(a) (10 pt) Show that if we run Gale-Shapley algorithm with men proposing, then m1
is matched to w1
and m2
is matched to w2
.
(b) (10 pt) Show that in every stable matching, m1
, m2 are matched to w1
, w2
, i.e., (m1
, w1
),(m2
, w2
) or
(m1
, w2
),(m2
, w1
) must be part of any stable matching.
3. (15 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
2.5
• f2
(n) = p
2n
• f3
(n) = n + 10
• f4
(n) = 10n
• f5
(n) = 100n
• f6
(n) = n
2
log n
4. Let f (n) and g(n) be positive functions (for any n they give positive values) and f (n) = O(g(n)). Prove or
disprove each of the following statements:
(a) (6 pt) g(n) = Ω(f (n))
(b) (6 pt) f (n)· g(n) = O(g(n)
2
)
(c) (6 pt) 2f (n) = O(2
g(n)
)
5. (12 pt) Given a list of numbers a1
, . . . , an
, we say it is a palindrome if the list reads the same backwards as
forwards (a1
, a2
, . . . , an
is the same with an
, an−1
, . . . , a1
). Assume these n numbers are stored as a linked
list, design an O(n) time algorithm to check whether it is a palindrome. Note that your algorithm is only
allowed to use O(1) additional memory.
6. Given a sequence of numbers [5, 8, 2, 10, 12, 14, 1, 20, 6, 15], answer the questions below.
• (5 pt) Please draw the corresponding Min Heap after inserting this sequence. The insertions are
performed with the exact order of the sequence. Please follow the algorithm we talked in the class (or
equivalently, Chapter 2, “Implementing the Heap Operations” subsection in the textbook).
• (5 pt) Please draw the corresponding Max Heap after inserting this sequence. The insertions are
performed with the exact order of the sequence.
• (15 pt) Now we want to design a new data structure “Medium Heap”, where the structure supports
two operations: 1) “push” Insertion of an integer, and 2) “find-medium” output the current medium
value (without deleting it). Note that for a1 ≤ a2 ≤ ··· ≤ an
, the medium is defined as an/2
if n is
odd, or (an/2 + an/2+1
)/2 if n is even. Design a data structure and an algorithm to support push and
find-medium in O(log n) time where n is the number of elements in the Medium Heap. (Hint: use a
min heap and a max heap together.)
Æ 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.
