Homework 1 Solution

Description

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 m₁, m₂ be two of the men and w₁, w₂ be two of the women in an instance of the Stable Matching Problem with n men and n women. Assume m₁, m₂, w₁, w₂’s preference lists are:

m₁’s preference: w₁ > w₂ > . . .

m₂’s preference: w₂ > w₁ > . . .

w₁’s preference: m₂ > m₁ > . . .

w₂’s preference: m₁ > m₂ > . . .

So, we only know the favorite and the second favorite of each of these four persons.

1. 1. (10 pt) Show that if we run Gale-Shapley algorithm with men proposing, then m₁ is matched to w₁ and m₂ is matched to w₂.

1. 2. (10 pt) Show that in every stable matching, m₁, m₂ are matched to w₁, w₂, i.e., (m₁, w₁), (m₂, w₂) or (m₁, w₂), (m₂, w₁) 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)).

f₁(n) = n^2.5

p

f₂(n) = 2n

f₃(n) = n + 10 f₄(n) = 10ⁿ f₅(n) = 100ⁿ

f₆(n) = n² 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))

1. 2. (6 pt) f (n) g(n) = O(g(n)²)

1. 2. (6 pt) 2^{f (n)} = O(2^g(n))

5. (12 pt) Given a list of numbers a₁, . . . , a_n, we say it is a palindrome if the list reads the same backwards as forwards (a₁, a₂, . . . , a_n is the same with a_n, a_{n 1}, . . . , a₁). 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.

5. 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 a₁ a₂ a_n, the medium is defined as a_n=2 if n is odd, or (a_n=2 + a_n=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 L^AT_EX, L_YX 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.