Homework 1 Solution

    1. (10 pt) Decide whether you think the following statement is true or false. If it is true, give a short explana-tion. 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) = n2.5
p

f2(n) =  2n

f3(n) = n + 10 f4(n) = 10n f5(n) = 100n

f6(n) = n2 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(2g(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.