A men and women's assignment can be created using the postponed acceptance procedure. Members of one gender act as suitors in this algorithm, while members of the opposite gender act as suitees. Every suitor whose proposal was rejected in the previous round makes a proposal to his or her highest-ranking suitee who has not yet rejected this suitor in the algorithm's sequence of rounds. Except for the suitor who ranks highest among all the suitors who have proposed in this round or prior rounds, the suitees reject all the proposals. This highest ranking suitor's proposal is still pending and will be rejected if a more alluring suitor makes a proposal in a later round. The series of rounds ends when every suitor has exactly one pending proposal. All pending proposals are then accepted. a) Write the deferred acceptance algorithm in pseudocode. b) Show that the deferred acceptance algorithm terminates. c) Show that the deferred acceptance always terminates with a stable assignmen
A men and women's assignment can be created using the postponed acceptance procedure. Members of one gender act as suitors in this
a) Write the deferred acceptance algorithm in
pseudocode.
b) Show that the deferred acceptance algorithm
terminates.
c) Show that the deferred acceptance always terminates
with a stable assignment
Step by step
Solved in 4 steps
