Description

General HW guidelines
• Each student should submit an individual solu on.
• For clarifica ons or any other help, you are welcome to use the course forum in Piazza.
Technical instruc ons
• Submit your solu on electronically via the course Moodle page.
• Submit your solu on as a single PDF file of size up to 10MB.
• The orienta on must be portrait and the page size must be A4 (the right propor ons are not enough; the grading tool does not support zooming or rota on).
• Make sure pages are properly ordered and oriented, and text is highly readable: large enough, sharp, in focus, and in high contrast with the background.
• Do not type in your answers as PDF comments (the grading tool ignores comments).
GOOD LUCK!

Question 1 (15 pts.)
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 (20 pts.)
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 (25 pts.). 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 (20 pts.). 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 (20 pts.). (20 pts.) N points are placed in a unit square. Show that the distance between the closest pair is O(1/N).