Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
EECS457: Advanced Algorithms
Due: Oct 9
Homework 1
You may discuss the assignments with your classmates but need to write down your solutions independently. Be careful with your handwriting. Unclear solutions will be assumed to be wrong.
1. For a woman w, we say that m is a valid partner if there is a stable matching that contains the pair (m, w). We say that m is the worst valid partner of w if m is a valid partner of w, and no man whom w ranks lower than m is a valid partner of hers. Prove that in the Gale-Shapley algorithm, each woman is paired with her worst valid partner.
2. Consider a town with n men and n women seeking to get married to one another. Each man has a preference list that ranks all the women, and each woman has a preference list that ranks all the men. The set of all 2n people is divided into two categories: good people and bad people. Suppose that for some number k, 1 ≤ k < n, there are k good men and k good women; thus there are n − k bad men and n − k bad women. Everyone would rather marry any good person than any bad person. Formally, each preference list has the property that it ranks each good person of the opposite gender higher than each bad person: its first k entries are the good people in some order, and its next n − k are the bad people in some order. Show that in every stable matching, every good man is married to a good woman.
3. Given a > 0 and b > 0, what does the following algorithm print? Prove your answer.
x, y, u, v := a, b, a, b
do
x > y → x, u := x − y, u + v
y > x → y, v := y − x, v + u
od
print ((x + y)/2); print ((u + v)/2);
4. Exercise 4.6
5. Exercise 4.52