The Stable Matching problem is solved with the Gale-Shapley algorithm. Here is t

Question

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

Explanation / Answer

a)

A man changes status from free to engage===5

A man changes status from engage to free===11

A man changes status from free to engage===5

A man changes status from engage to free===11

b)

engaged

c)

neither

d)

Stritly increasing

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.