Stable Matching Problem, algorithm trace. Write out the steps for the algorithm described in Algorithm Design by Jon Kleinberg and Eva Tardos, to determine a stable matching. Then, list all matching that are not stable.

Stable Matching Problem, algorithm trace. Write out the steps for the algorithm described in Tardos, to determine a stable matching. Then, list all matchings that are not stable. Preference lists: M1(4,3, 1, 2) M2(1, 3,2, 4) M3(4, 1,2, 3) M4(1, 2,3, 4) W1(1,2, 3,4) W2(2, 4, 1,3) w3(1, 2, 3, 4) w4(4, 1, 3, 2) Initially all men and women are free While there is a man m who is free and has not proposed to every woman Choose such a man m Let w be the highest-ranked woman in m's preference list to whom m has not yet proposed If w is free then (m, w) become engaged Else w is currently engaged to m If w prefers m' to m then m remains free w prefers m to m' (m, w) become engaged m' becomes free Else EndIf EndIf EndWhile Ret set of engaged pairs Stable Matching Problem, algorithm trace. Write out the steps for the algorithm described in Tardos, to determine a stable matching. Then, list all matchings that are not stable. Preference lists: M1(4,3, 1, 2) M2(1, 3,2, 4) M3(4, 1,2, 3) M4(1, 2,3, 4) W1(1,2, 3,4) W2(2, 4, 1,3) w3(1, 2, 3, 4) w4(4, 1, 3, 2) Initially all men and women are free While there is a man m who is free and has not proposed to every woman Choose such a man m Let w be the highest-ranked woman in m's preference list to whom m has not yet proposed If w is free then (m, w) become engaged Else w is currently engaged to m If w prefers m' to m then m remains free w prefers m to m' (m, w) become engaged m' becomes free Else EndIf EndIf EndWhile Ret set of engaged pairs