A. What is one event that occurs each time the loop body is executed? B. How man
ID: 2247598 • Letter: A
Question
A. What is one event that occurs each time the loop body is executed? B. How many women could one man propose to in a run of the Gale-Shapley algorithm? C. Thi s helps us see an upper bound on the number of total proposals. Therefore, what is an upper bound number of times the while loop could execute, if there are n men and n women? D. If a run of the Gale-Shapley algorithm terminated with a free man left at the end, what is the maximum number of women who can be engaged and what do we know about him? (hint: loop conditional) E. Using the fact from before that "if a woman has been proposed to, she remains engaged for the rest of the algorithm", how many women are engaged? F. What did you just prove by contradiction? G. If a man called m ends up with a woman wat the end of an execution of Gale-Shapley, he must have proposed to each woman above w in his preference list. One of which two things must have happened between m and each woman above w in m's preference list?Explanation / Answer
A. Loop condition checking
beacuse every time we need to check the loop condition before entering the loop body.
Please ask other questions as separately as per chegg policy.