In our discussion of the Gale$-$Shapley algorithm, we used the number of offers as a measure of

progress and showed that each iteration of the while loop makes one new offer of a position to an

applicant. Since there are n applicants and n positions, and an applicant can never be offered a

position more than once, the while loop can be executed at most n

$2$

times.

Consider a simple instance of Gale$-$Shapley, where n $=3($there are $3$ open positions, A$,$ B$,$ and

C and $3$ applicants X$,$ Y $,$ and Z$).$ Provide an example execution of Gale$-$Shapley that results in

the maximum possible number of offers made $($i$.$e$.,$ executions of the while loop$).$ You will need

to provide the complete preference list of all three positions and all three applicants as well as the

order in which positions are offered to applicants. Also state whether your free list is a LIFO queue

or a FIFO queue $($that is$,$ is a position that becomes open because an applicant took a better offer

immediately offered their next favored applicant or do they go to the back of the line?$).$

Finally, summarize at least three generic observations this exercise helps you make about the

Gale$-$Shapley algorithm$$s execution. We$$ve done the first one for you.