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.
Model Answer:
1. Jack proposes to Alice and is paired with Alice
2. Fred proposes to Amy and is paired with Amy
3. Tom proposes to Alice and is paired with Alice; Jack is no longer paired and is placed on the stack
4. Jack proposes to Amy but is rejected
5. Jack proposes to Lily and is paired with Lily
6. Sam proposes to Amy and is rejected
7. Sam proposes to Lily and is rejected
8. Sam proposes to Alice and is rejected
9. Sam proposes to Sue and is paired with Sue
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.
Program Analysis Model Answer:
1st 2nd 3rd 4th M1 W4 M2 W4 M3 W4 M4W4W2W3W1
Term 1, 2015
1st 2nd 3rd 4th W1 M4 W2 M4 W3 M4 W4M4M2M3 M1
W1
W2
W3
W2
W1
W3
W3
W2
W1
M1
M2
M3
M2
M1
M3
M3
M2
M1
M1 must be paired with W1, M2 must be paired with W2, M3 must be paired with W3 and M4 must be paired with W4. If any of these pairings is not made, the pair would elope because they prefer each other over all other options.
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.
Model Answer:
1st 2nd 3rd 4th M1 W4 M2 W4 M3 W4 M4W4W2W3W1
1st 2nd 3rd 4th W1 M4 W2 M4 W3 M4 W4M4M2M3M1
W1
W2
W3
W2
W1
W3
W3
W2
W1
M1
M2
M3
M2
M1
M3
M3
M2
M1
The first choice of each man will produce a woman who is free, so after 4 itera- tions the algorithm will terminate with a stable match.
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.
Model Answer:
1st 2nd 3rd 4th M1 W4 M2 W4 M3 W4 M4W1W2W3W4
1st 2nd 3rd 4th W1 M4 W2 M4 W3 M4 W4M1M2M3M4
W1
W2
W3
W1
W2
W3
W1
W2
W3
M1
M2
M3
M1
M2
M3
M1
M2
M3
• The worst case is produced by always chosing the free man with the highest index (i.e. M4 before M3 before M2 before M1).
• M4 is paired with W1 then W2 then W3 then W4 • M3 is paired with W1 then W2 then W3
Program Analysis Term 1, 2015 • M2 is paired with W1 then W2
• M1 is paired with W1
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:
(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.
Model Answer:
• A stack can be used to hold the set of currently un-matched men. Choosing a man to consider at the start of the while loop involves popping the top element of this stack, which can be performed in constant time. If a man becomes free then he is pushed on to this stack. Initially, all men are placed on this stack in constant time. A queue could also be used, but since the order in which un-matched men are considered does not matter, the slightly easier to implement stack would make a good choice here.
• For each man a stack can be used to hold his preferences. These are stored in order of decreasing preference. For a man m, the identify of the next woman whom he has not yet proposed to is found by popping this stack in constant time. While the algorithm is running, nothing is added to these stacks.
• An array with current engagement information in it. There will be one po- sition for each woman and at that position will be the ID of a man she is currently engaged to, or NIL if she is not yet engaged.
• The preference information for the women can be held in a two dimensional array, one entry (array) for each woman. The entry for a woman w contains an array (indexed by men) that returns the rank of that man among the pref- erences of w. This will allow a comparison between her preference between two men to be established in constant time.
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
Program Analysis Term 1, 2015
Model Answer: These are standard data structures and any textbook that dis- cusses datastructures and algorithms will cover this in detail.