Computer Science 320
Programming Assignment 1
Requirements
This first assignment lets you get familiar with stable maching problem. We would like you to implement the Gale-Shapley algorithm for finding the man-optimal stable maching. An O(n^2 ) solution is preferred since we have set the running time limit on the automated marker. Some tricks to speed up the process of proposing are highly recommended.
There are 3 test cases whose sizes are different. The first one contains 50 pairs, while the last largest one comprises of 1000 pairs. It is worth 5% of your total course marks. The first and second test cases have 2 marks each and the last has 1 mark.
In order to boost your performance, we have created an additional small test case, namedR5, which does not contribute to the mark. It would help you to be familiar with reading input and printing output on the automated marker.
There will be a penalty if you exceed the submission limit of 8. Therefore, pleasetest your implementation with your own generated inputs before submitting to the automated marker.
Test case description
We use # for the comment and we have e.g. n= 5 to indicate the valuenof our stable matching problem. We use all odd integers ranging from 1 to 2n−1 as the man ID, and all even integers ranging from 2 to 2nas the woman ID. There is a whitespace after #,n, =, : to make the parsing process easily.
The preference for each person ID comes after the colon : (no whitespace between person ID and the colon). There is a whitespace between each integer on the preference list. For example,1: 2 6 8 4 10 means that the man ID 1 has the preference list{ 2 , 6 , 8 , 4 , 10 }where his best choice is 2 and worst
choice is 10.
You should output the matching pair, starting from the man ID 1 to the man ID 2n−1. The matching format ism wwheremis the man ID andwis the woman ID. Note that there is one whitespace betweenmandwin the output format.
Sample Input:
Random instance for Gale-Shapley, n = 5
#
n = 5
#
1: 2 6 8 4 10
2: 5 9 3 1 7
3: 6 8 10 4 2
4: 3 9 7 5 1
5: 2 6 8 10 4
6: 7 3 9 5 1
7: 10 8 4 6 2
8: 5 7 1 3 9
9: 2 4 6 10 8
10: 5 9 7 3 1
Sample Output:
1 8
3 6
5 2
7 10
9 4
Submission Procedure
Submit your program solutions tohttps://www.automarker.cs.auckland.ac.nz. There will be a penalty of 20% (per test case) if you exceed the submission limit of 8 for each test case (applied if you
eventually solve them).