A. What is one event that occurs each time the loop body is executed? B. How man

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.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.