The Stable Matching problem is solved with the Gale-Shapley algorithm. Here is the description of the Gale-Shapley algorithm from the Kleinberg text. It talks about a matching between equal numbers of men and women. 1 Initially all mEM and weW are free 2 While there is a man m who is f ree and hasn't proposed to every woman Choose such a man m Let w be the highest-ranked woman in m's preference 1ist to whom If w is free then (m, w) become engaged Else w is currently engaged to m m has not yet proposed If w prefers m' to m then m remains free Else w prefers m to m (m, w) become engaged m becomes free 10 Endif 12 13 Endif 14 Endwhile 15 Return the set s of engaged pairs 2 Basics A. Find the part in the algorithm, and write the line numbers below, where: a man changes status from free to engaged a man changes status from engaged to free a woman changes status from free to engaged a woman changes status from engaged to free