--------------------------------------------------------------------------------------- CS210 Introduction to Java Programming Assignment FOR MORE CLASSES VISIT
( 3 ) Use the confluence property of the deferred acceptance algorithm . Problems 1 through 3 above are concerned with modifying an SMI instance I by adding a new man . We now consider a way to modify an SMI instance without adding a new agent . For any SMI instance I , any woman q in I , and any man p in I who is single in da ( I ) and considers q to be unacceptable , we define extend ( I , p , q ) as the SMI instance I 0 that is identical to I except the preferences of man p are modified as follows : man p moves woman q from his unacceptable set to the the least-preferred position in his ordered list of acceptable women . The arguments used for solving Problems 1 , 2 , and 3 are easily adapted to establish Lemma Extend below ; the proof is omitted . Lemma Extend . Let I be an SMI instance , let q be a woman in I , let p be a man in I who is single in da ( I ) and considers q to be unacceptable , and let I 0 denote the SMI instance extend ( I , p , q ). If q prefers p to threshold ( I , q ), then p is matched to q in da ( I 0 ); otherwise , p is single in da ( I 0 ) and threshold ( I 0 , q 0 ) = threshold ( I , q 0 ) for every woman q 0 i
--------------------------------------------------------------------------------------- CS210 Introduction to Java Programming Assignment FOR MORE CLASSES VISIT