Suppose that the matching problem is to match nm men to nw women, where nw
(a) Describe in detail the generalization of the Gale-Shapley algorithm for this case. Prove that the algorithm terminates with a stable matching.
(b) What is the maximal number of stages in the men's courtship algorithm?
(c) Construct an example where nm > nw such that the men's courtship algorithm runs through the maximal number of stages.