1. Consider the generalization of stable matching problem where a certain man-woman pairs are forbidden. The set of forbidden pairs is denoted as F. Each man m ranks all the woman w for which (m, w) ¢...

Extracted text: 1. Consider the generalization of stable matching problem where a certain man-woman pairs are forbidden. The set of forbidden pairs is denoted as F. Each man m ranks all the woman w for which (m, w) ¢ F and each woman w ranks all the man m for which (m, w) ¢ F. Consider the following algorithm for finding a stable matching that consists of only unforbidden pairs: Initially all mE M and w e W are free; S = Ø While there is a man m who is free and hasn't proposed to every woman w for which (m, w) ¢ F Choose such a man m Let w be the highest-ranked woman in m's preference list to which m has not yet proposed If w is free: Add (m, w) to solution S Else (w is current matched with m'): If w prefers m' to m m remains free Else Replace (m', w) by (m, w) in S Return solution S Answer true or false for the following questions: (a) Any woman w remains engaged from the point at which she receives her first proposal, and the se- quence of partners to which she is engaged get better and better. (b) If a man m is free at the end of the algorithm, then he must have proposed to every non-forbidden woman. (c) If a woman w is free at the end of the algorithm, then it must be that no man ever proposed to w. (d) At the end of the algorithm, there can be a man m and a woman w, such that (m, w) & F , but neither of which is part of any pair in the matching S. (e) At the end of the algorithm, there can be a pair (m, w) e S and a man m' that is free, (m', w) ¢ F , but such that w prefers m' to m.