COMP 482 Sample Ch 1

COMP 482 Sample Problems: Intro/Stable Marriage Every quiz will have 3 problems. Officially, the questions could be on anything covered earlier in the class. More typically, they will be on the oldest material on which you haven’t been quizzed. There will typically be at least 1 problem which is straightforward (eg run an algorithm that was taught to you on a given input) and at least 1 that takes some independent thought. Problem 1. (10 points) For eqch of the following statements determine whether it is true of false. (+1 for a correct answer, -0.5 for an incorrect answer, 0 for a blank). Binary search (bisection search) finds the item even if the array is not sorted. A problem and a problem instance are the same thing. An algorithm for a problem and a solution for an instance are the same thing. Every instance of StableMarriage has at least one stable matching. There is an instance of StableMarriage with n = 4 and 30 stable matchings. In every instance of StableMarriage there is a stable matching where at least one of the men gets his first choice. It is possible that an instance of StableMarriage has 4 stable matchings. Some instances of StableMarriage have no stable matchings. The stable matching found by ProposeDispose does not depend upon the order in which the men propose. The person answering taking this quiz wants to fail the class. Problem 2. (10 points) Solve the following instance of StableMatching using the Propose-Dispose algorithm. Show enough work to convince me that you aren’t just guessing or using brute force. M1 M2 M3 M4 M5 W1 W1 W2 W2 W1 W2 W3 W3 W1 W5 W3 W2 W1 W4 W4 W4 W5 W4 W3 W3 W5 W4 W5 W5 W2 W1 W2 W3 W4 W5 M4 M5 M3 M5 M4 M5 M2 M2 M3 M1 M2 M3 M4 M2 M3 M3 M1 M5 M1 M2 M1 M4 M1 M4 M5 Problem 3. (10 points) For the instance of StableMarriage below determine whether the matching {(M1 , W3 ), (M2 , W4 ), (M3 , W2 ), (M4 , W5 ), (M5 , W1 )} is stable and justify your answer. Same questions for {(M1 , W5 ), (M2 , W2 ), (M3 , W3 ), (M4 , W1 ), (M5 , W4 )}. M1 M2 M3 M4 M5 W1 W1 W2 W2 W1 W2 W3 W3 W1 W5 W3 W2 W1 W4 W4 W4 W5 W4 W3 W3 W5 W4 W5 W5 W2 W1 W2 W3 W4 W5 M4 M5 M3 M5 M4 M5 M2 M2 M3 M1 M2 M3 M4 M2 M3 M3 M1 M5 M1 M2 M1 M4 M1 M4 M5 Problem 4. (10 points) For some instances of StableMatching running the Propose-Dispose algorithm will result in a person being paired with his (or her) most preferred (ie highest ranked/first choice) partner. Give an instance of StableMatching where the Propose-Dispose algorithm yields a matching where strictly more women get their most preferred man than men get their most preferred woman. Problem 5. (10 points) Solve the following instance of StableMatching using the Propose-Dispose algorithm. Show enough work to convince me that you aren’t just guessing or using brute force. M1 M2 M3 M4 M5 W1 W4 W4 W4 W1 W2 W3 W3 W1 W5 W3 W2 W1 W3 W4 W4 W5 W2 W2 W2 W5 W1 W5 W5 W3 W1 W2 W3 W4 W5 M4 M5 M3 M5 M4 M2 M2 M2 M1 M1 M3 M3 M4 M4 M3 M5 M1 M5 M3 M2 M1 M4 M1 M2 M5 Problem 6. (10 points) For some instances of StableMatching running the Propose-Dispose algorithm will result in a man proposing to all of the women. F F F T F F T F T F Give an instance of StableMatching with n = 4 (ie 4 men and 4 women) where the Propose-Dispose algorithm results in a man proposing to all 4 women. Problem 7. (10 points) Let I be an instance of StableMarriage with all men having identical preference lists. Show that I has exactly one stable matching. Problem 8. (10 points) Problem 1 on page 22 of the textbook. Decide whether the following statement is true of false. If it is true, give a short explanation why it must be true. If it is false, give a counter example. In every instance of StableMatching, there is a stable matching containing a pair (m, w) such that m is ranked first on the preference list of w and w is ranked first on the preference list of m. Problem 9. (10 points) For a man m, define Valid(m) to be the set of women who are matched with m in some stable matching. For a man m define BestValid(m) to be the woman in Valid(m) that m most prefers. Show that two di↵erent men m and m0 cannot have BestValid(m) =BestValid(m0 ). Problem 10. (10 points) Johnny Backwards misunderstood the ProposeDispose algorithm. He thinks a man propose to the lowest ranked woman who has not yet rejected him. Will this algorithm always terminate? Will it always give a stable matching? Will it ever give a stable matching? Problem 11. (10 points) Either find an instance of StableMarriage with at least 4 stable matchings (the smaller the example the better) or prove there are never more than three di↵erent stable matchings M1 WX - M2 M3 - W3-W4 WX-W3 - 2 - M4 12 - -WK WI - - - - - a M1 M1 ⑤ - - all no W , W2 M2 v ~ - WI M2-W3 good instability ~ X instability . M2 M3 MI WI W3 W2 WI M1 M2 WI W2 W3 w2 M2 M1 M3 M3 WIWZW3 W3 M3 M2M1 M1 - WI M2 - y-w2 M3-W-w/2-w3 as you their got man got can first his see all choice first the woman & only one choice. M1-WX-WX-W - M2-WA-W/3-Wa M3-W-Wa My-WH-Wr Ms-W-Ws Wy m1 WLW3 m2 W2 m3 W3 W1 W m4 WI W3W4 m1 - m2 W2 NH WY Wa W3 WI WH M3 M4 M2 WI M1 W2 M2 M1 W3 M3 M4 M2 M1 W4 M4 M3 M3 M4 M2 M1 WI W2 - m3- W3 my -NA-wX-w/-w4 as you all Four man a proposed to . woman M1 WI WZ M2 WI W2 M3 WI W2 M1 see can WI Wa W3 M1 W2 WS WS M3 M2 M2 M3 M1 M3 M2 M1 WI - M2-wX-w2 M3 WX-wX-w3 - This All She shows the will that man pick satisfiedI get the boys so the ith exactly there is will propose she who will not who to prefers leave women get's same so , each hasn't been her stable one matching . and woman they other . engaged favorite both will All the and man be woman next . M1 M2 WI W2 WI W2 M1 WI W2 M2 shows the their first if So M1 WI - M2 - false is This M2 M1 his Claim For : different two any , matching problem Bestvalid (m) + BestValid Proof BestValid(m) : the all let's do an M1 - WI Il MI did which M2- W2 the so that which is not is get M2 . impossible = and me in a preferredbe women m can by m . matched ~ mi = M2 , GW2 WIS , BestValid (m) BestValid (m') = after looking two man WI = first this to have , GW1 N23 = wa, her In got pair (m w) M2-Wr Valid (m) who M1 , Mrz M1-W2 Valid (m') So M2 M we ~ m at all. instance WI M WW at stable (mi) whom woman get choic we men m most is the did not choice situation , it's a list look first choice preference women we but W2 the , Wa at this can't we have can same prove BestValid . in the set of Claim : The It is Proof : Backwards Johnny algorithm will always terminate. will not always give a stable matching but it . possible to give a stable matching though will his It are of finite number terminate after preference list & will go through every There are to until women and it women in is . inverted all the men . engaged matching . So end always not would algorithm The stable W3 We WI WI M3 M2 M1 M2 W2 W I W2 W2 M2 M1 M3 M3 W , W2 W3 w3 M1 M3 M2 M1 - M2 WI M3 This W2 - - not is prefers partner will there Well will give you M1 W3 We M2 We wa w W3 W I M1 are - M2 - M3 wi W2 - W3 w i W so M1 , some over this run current they together . instances WI M1 w2 M2 M1 W3 M3 M2 M1 this is W3 her mean stability Stable W3 prefers partner & his over stable M1 because W3 up being : M1 M3 the it that get We women , proposes man a & men M3 M2 M3 where it MI WI W2 WS Wa Wi M2 M1 M4 M2 W2 we WY W3 W2 M1 M2 M3 M4 M3 W3 WY WI ws M4 M3 M2 M1 MY WYW3 W2 WI W4 M3 M4 M1 M2 WI M1 M1 - M2 W2 - M3 M1 - W2 WI - M2 - M2 W) M3 W3 M3- 14 M4-INY - M1 WZ M1 - - We - M2 WI - M3 - M3 - W W3 M4 -14 WH W3 M4- W3 we Wi M2 M3 M4 M1 wo wa v2 M3 M4 M1 M2 we wa was M4 M1 M2 M3 wz ws wa Wy M M2 M3 M4 MI We We was M2 We ws M3 W3 wo My we M1 We wi M2 WI We M3 w , We My Wi We was wa wa wa wa wh we wa / WI M2 MS M4 n2 M3 My M1 M2 W3 M4 M1 M2 M3 wa M , M2 M3 M4 M1