# 算法分析代写 | CS 5300 01 Advanced Algorithm Design and Analysis

The goal of this homework is to implement the stable matching algorithm in the Algorithm Design book presented on page 6.

1. Create a python file named “stable_matching_id#”, with id# corresponding to your student ID number. For example, if my student ID is 1234567, I would create a python file “stable_matching_1234567”.
2. Your program should read in an input text file that contains the number of men and women to be paired, the preferences of each man, and the preferences of each woman. For example, for a stable matching problem involving 3 men and 3 women, the input file should have the format. The first argument represents the number of men and women in the stable matching problem. The second argument represents the preferences of each man. In this example, the first man has preference {1,2,3}, the second man has preference {2,1,3}, and the last man has preference {3,1,2}. The last argument represents the preferences of each woman. In this case, the first woman has preference {1,2,3}, the second woman has preference {2,3,1}, and the last woman has preference {3,2,1}. See the input files for more examples.
1. Create a function named stable_matching that takes in the number of men, the number of women, the preferences of the men, and the preferences of the women. The function should output a set of a stable matching. Hint: A woman should only break an engagement to her current fiancée if a man of higher preference proposes to her.
2. The stable matching should be sorted by the number of each man in the pair. For example, {(2, 1), (1, 2)} would be considered an incorrect stable matching, whereas {(1,2), (2,1)} would be an acceptable stable matching.
3. You can further test your program by creating input text files following the format of the sample input text files provided.
4. If you get stuck or have any questions, please feel free to email me at [email protected] I will try to get back to you as quickly as possible. It is better to contact me during the week, as I am less responsive on the weekend because, well, it is the weekend. This does not mean that I will not respond to your emails on the weekend, it only means that the response time will be longer than it would be during the week. However, I will do the best I can to respond as quickly as possible.