Stable Matching Problem, algorithm trace. Determine a stable matching by following the Gale-Shapely algorithm described in Tardos and in lecture and as given below. You only need to provide what the algorithm returns at the end. Preference lists: MI(1,3,4, 2) M2(1, 3, 4,2) M3(4, 1, 2, 3) M4(1, 2, 3, 4) w1(1, 2, 3, 4) W2(2, 4, 1, 3) W3(1, 2, 4, 3) W4(4, 1, 2, 3) Initially all men and women are free While there is a man m whe he 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 Else w prefers m to m (m, w) become engaged m' becomes free Endlf Endlf End While Ret set of engaged pairs