Python代写 | Computer Science 320 Programming Assignment 1

本次cs代写主要为python编程相关的assignment

This rst assignment lets you get familiar with stable maching problem. We would like you to implement
the Gale-Shapley algorithm for nding the man-optimal stable maching. An O(n2) 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 dierent. The rst one contains 50 pairs, while the last largest
one comprises of 1000 pairs. It is worth 5% of your total course marks. The rst 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, named R5, 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, please test your imple-
mentation with your own generated inputs before submitting to the automated marker.

We use # for the comment and we have e.g. n = 5 to indicate the value n of 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 2n as 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 f2; 6; 8; 4; 10g 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 is m w where m is the man ID and w is the woman ID. Note that there is one whitespace
between m and w in 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
1
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