Question 1
Consider an input to the stable pairing problem with n men and n women. Out of the n men, there are k smart men and n-k stupid men. Also, there are k smart women and n-k stupid women (for some k between 1 and n-1). Everyone would rather marry any smart person than any stupid person (so the first k entries in any preference list are of smart people of the opposite gender in some order). Prove that in every stable pairing, every smart man is matched with a smart woman.
Question 2
In class we argued that the Traditional Marriage Algorithm will never require more than n2 days to terminate. In fact, it is possible to prove a tighter upper bound, n2 -2n+ 2, on the maximum number of days until the algorithm terminates. Describe a set of preference lists that requires n2 -2n + 2 days to terminate. Your answer should be general: Given n, describe the preference lists of boy k for k=1..n, and of girl k for k=1. Explain why n2 -2n + 2 days are needed until termination.
Clarification: The last day in which no one is rejected is also counted.
Question 3 . Solve the following recurrence relations and give a bound for each of them. When it is applicable (not always), you can use directly the Master Theorem. In all questions, assume that T(1)=(1).
1. T(n) = 6T(n/4) + n
2. T(n) = 16T(n/2) + n4
3. T(n) = 3T(n/27) + 3
4. T(n) = T(n - 1) + nc, where c ≥ 1 is a constant
5. T(n) = T(n - 1) + cn, where c > 1 is a constant
Question 4 . Assume that you are consulting to an investment company. You have a magical power to predict exactly the daily price of some stock in the coming n days. Formally, for each day i=1,2,..n, you know p(i) - the price of the stock at day i. You need to determine in what day to buy and in what day to sell some amount of this stock in a way that maximizes the profit (or determine that this stock should never be traded in the coming n days). You can perform a single buy and a single sell.
For example, if n=3. p(1)=9, p(2)=1, p(3)=5, then you should return: "buy on day 2, sell on day 3". Suggest an algorithm based on divide and conquer for solving the problem in time O(n log n). Describe the algorithm, justify its correctness and time complexity.
Question 5 . N points are placed in a unit square. Show that the distance between the closest pair is O(1/N).
