Implement a program for determining whether an assignment of women to men is stable or not as discussed in class. For this assignment you must use Python 3 or higher to implement your algorithm as it is relatively straightforward. Further, the goal is to help you understand the notion of stability, so make sure to test it adequately. For an efficient implementation, minimize the number of “potential cause of instability” checks, that is, the number of (woman, man) pairs to be checked to ensure that the solution is (un)stable. Name your main Python script as assignment1.py, and make sure your code is well-documented.

(a)Assume that the input file (stableInput.txt) is a sequence of (2 + 2*n + n*m)-lines, with (i) n in the first line on its own signifying the number of women and men, (ii) m in the second line signifying the number of assignments to be tested, (iii)  the following (2*n) lines encoding the preference lists – n lines for women and n lines for men – each containing space separated list of (n+1) names as required in the stable marriage problem, and (iv) and n*m lines encoding m-assignments, each assignment given as n-lines, each line containing a woman-man pair, as follows:

For example:

2

         3

         Alice      Xavier  Zeus

         Carol      Zeus    Xavier

         Xavier     Alice   Carol

         Zeus       Alice   Carol

            Alice      Xavier

            Carol      Zeus

            Alice      Xavier

            Carol      Zeus

            Alice      Zeus

            Carol      Xavier

(b)Write the output as m-lines, each line containing three numbers, with either 1 or 0 to signify whether or not the assignment is a stable match, followed by n2, followed by the number of unassigned pairs the algorithm checks to determine stability or rule out instability.  You must name input file, output file, and the Python program as follows: stableInput.txt, stableOutPut.txt, assignment1.py. Points will be deducted if you do not follow this naming convention and file extension. 

For example, for the above input, one possible output can be:

            1   4   0

            1   4   0

            0   4   1

Answer rating: 100% (QA)

ANSWER A The program below implements a solution for the stable marriage problem as discussed in class It takes as input a sequence of 2 2n nmlines with i n in the first line on its own signifying the ... View the full answer