Program Analysis Problem Sheet 1
Here is the Gale and Shapley algorithm for the Stable Match problem.
Initialize each person to be free
while there’s a free man who hasn’t proposed to every woman
Choose one such man m
Let w be 1st woman on m’s list to whom m not proposed if w is free
assign m and w to be engaged else if w prefers m to her fiance ́ m′
assign m and w to be engaged, and m′ to be free else
Term 1, 2015
w rejects m
1. Use the Gale and Shapley algorithm to find a stable match given the following
preferences. 1st
2nd
Lily
3rd 4th 1st Sue Alice
Sue Lily
Amy Sue
2nd
Sam
3rd 4th Jack Tom Jack Jack Tom
Alice
Amy
Lily
Amy
Alice
Lily
Alice
Sue
Lily
Tom
Fred
Sam
Jack
Fred
Sam
Tom
Fred
Sam
Jack Fred Tom Sam
Amy
Alice Sue
Amy Fred
Assume that free men are held in a stack and that the initial order (from top to bottom of stack) is Jack, Fred, Tom, Sam. For simplicity, the man at the top of the stack is always allowed to propose first. Note the correctness of the algorithm does not depend on the order in which men propose.
2. Construct an instance of the Stable Match problem involving 4 men and women where there is only one possible stable match. Justify your answer.
3. Construct an instance of the Stable Match problem involving 4 men and women which illustrates the best-case running time of the Gale and Shapley algorithm no matter which of the free men is chosen in the first line of the while loop. Explain your answer.
4. Construct an instance of the Stable Match problem involving 4 men and women which illustrates the worst-case running time of the Gale and Shapley algorithm given at least one way that in which a free man is chosen in the first line of the while loop. Explain your answer.
5. Consider how the Gale and Shapley algorithm can be implemented in order to meet the requirement that the body of the while loop is executed in constant time.
In particular, you will need to identify:
Program Analysis Term 1, 2015
(a) the data that needs to be stored;
(b) the operations on this data that need to be supported in an efficient way; and
(c) which specific data structures meet these requirements.
6. For each of the following data structures, discuss the core functionality that must be provided and how this functionality can be provided in an efficient way.
(a) stack (b) queue
(c) priority queue (d) set