Python Programming Project
Project Handout CSE 2353 Project Assigned Nov 4th Due Dec 5th at 11:59pm “Stable Marriage” Problem A well-known problem in the field of Computer Science is known as the “Stable Marriage” problem. As it was defined, the problem describes a scenario where a set of men and an equally sized set of women are to be matched up for marriage while taking into account their preference of partners. In a more general case, this problem can be defined as the following: Suppose you have two distinct sets of elements, denoted A and B. Both sets have exactly n elements. Each element in set A is to be paired with another element in set B. Prior to pairing, all elements in A give high-to-low preference ranking showing which elements in B they want to be paired with, and vice-versa. A “stable pairing” is a set (denoted S) in which the following conditions hold true: 1. The set S must be a subset of A x B (cartesian product of A and B) 2. All elements in set A have a corresponding element in set B such that the pair (a, b) is an element of S 3. All elements in set B have a corresponding element in set A such that the pair (a, b) is an element of S 4. There are no two pairs (a, b) and (a’, b’) in S such that b’ is higher preference for a than b, and a is higher preference for b’ than a’ (in this case, since a and b’ both prefer each other to their assigned match, they will choose to break their match in favor of a match (a, b’)) 5. There are no two pairs (a, b) and (a’, b’) in S such that a’ is higher preference for b than a, and b is higher preference for a’ than b’ (again, in this case b and a’ would break their assigned match in favor of a match (a’, b) For example, consider students in CS 3345 and CS 3353 as two distinct sets of people (assume that you can’t enroll in both at the same time). Your sets may look like: A = { “Alex”, “Bob”, “Charles” } B = { “Devin”, “Erik”, “Frank” } Where A = CS 3345 and B = CS 3353. A joint project between the two classes requires forming pairs of students containing one student from each class. Prior to creating pairs, each student was tasked with defining who they want to work with, in order of high to low preference: Alex: Devin, Frank, Erik Devin: Charles, Bob, Alex Bob: Frank, Erik, Devin Erik: Bob, Charles, Alex Charles: Devin, Erik, Frank Frank: Bob, Alex, Charles A stable pairing of the two sets of students may look like the following: Alex & Erik Bob & Frank Charles & Devin This satisfies each constraint. In particular, there are no sets of pairs wherein two people from different pairs both prefer each other compared to their given partners. For example, while both Alex and Erik are lowest in each other’s preferences, they are also lower in everyone else’s preferences compared to their assigned partners. As such, no one will choose to leave their groups and the pairing is deemed “stable” (perhaps not ideal, but stable nonetheless). A generic solution to this problem has been defined in a seminal paper by David Gale and Lloyd Shapley, appropriately named the Gale-Shapley algorithm. You will need to do outside research on this algorithm in order to complete this project. The original paper is publicly available and easily found online. Your task is to do some research and theoretical analysis on how this algorithm works and demonstrate its correctness. Then, you will implement the algorithm so that it works with some provided constraints. Theory (40% of grade) On page 1 of this handout, there are 5 conditions that must be satisfied in order for a set to be considered a stable match. For each condition, convert it to formal logic. Be explicit and clear when it comes to defining things like your domains, your predicates, etc. Hint: most of them contain at least one kind of quantifier. Then, use the method of proof by contradiction to prove the following: • If both sets contain n elements, The Gale-Shapley algorithm always results in n pairs. • The resulting pairs are stable; as in, there are no unstable pairs when the algorithm finishes. Additional research will be required to understand and answer the above bullet points. In relation to the Implementation section below: outline an algorithm that can be used to verify that a set of matches are in fact stable. Write this algorithm in pseudocode. You will eventually convert this pseudocode into actual code in the next section. Your answers must be grouped into a single PDF file. Neatly handwritten or typed responses are accepted. Implementation (60% of grade) Your implementation of the Gale-Shapley algorithm can be done in any of the following languages: Java, C++, Python, or JavaScript (node). You must implement the algorithms from scratch. The following defines some Java-esque pseudocode for building those sets: class Element { String name; List
preferences; public Element(String name) { … } public String getName() { … } public void addPreference(Element pref) { … } public List getPreferences() { … } } class SetOfElements { List elementsInSet; public SetOfElements() { … } public void addElement(Element e) { … } public List getElements { … } } class StableMatchSet { List<>> matches; public StableMatchSet() { … } public void determineMatches(SetOfElements A, SetOfElements B) { … } public void addMatch(Element a, Element b) { … } public boolean matchesAreStable() { … } } You will likely need to add additional functions / data to complete this project. No matter what language you choose, your code must have a similar structure, with data types appropriate to that language. The implementation details are up to you to determine, but in general your implementation must satisfy the following constraints: • A Set contains a list / vector / array of Elements. The decision to use a list or vector or array depends on your choice of programming language. • An Element contains a string name and a list / vector / array of elements denoting their hierarchy of preferences. preferences[0] represents the highest priority choice, preferences[1] represents the second highest priority choice, etc. • The result of your algorithm must be another Set type, which contains a list / vector / array of pairs / tuples of elements, each denoting a match. • That Set type must have a matchesAreStable() function that runs a verification function to make sure your matches are in fact stable. It returns true if it is stable, false otherwise. This should be based on the pseudocode you defined in the Theory section. Your program will call that function after determining a stable match, and the results of that function call will be printed (see expected output below). Inputs Your program will need to read two files, each with the same format. The first line will have a number n representing the number of elements in the set. Each subsequent n lines will contain a string, followed by a colon, followed by strings separated by commas. This represents an element and their preferences ordered from highest to lowest preference. The string before the colon represents that elements name. The strings separated by commas after the colon represent the preference list for that element. So for the example above you would read two files: SetA.txt 3 Alex:Devin,Frank,Erik Bob:Frank,Erik,Devin Charles:Devin,Erik,Frank SetB.txt 3 Devin:Charles,Bob,Alex Erik:Bob,Charles,Alex Frank:Bob,Alex,Charles You can assume the following about these input files: • Both files will be well formatted • They will contain the same number of lines • The first line will be a number n ³ 3 (no upper limit though) • The preferences in file A exist as names in file B and vice-versa • There are no spaces in the files (except for new line characters) Outputs Your program is expected to output the following: • The elements in set A, with their preferences • The elements in set B, with their preferences • A stable pairing for those two sets • The output of your matchesAreStable() function Sample output is below. Match your output as closely as possible to this output. Set A contains: Alex: (Devin, Frank, Erik) Bob: (Frank, Erik, Devin) Charles: (Devin, Erik, Frank) Set B contains: Devin: (Charles, Bob, Alex) Erik: (Bob, Alex, Charles) Frank: (Bob, Alex, Charles) Stable Pairing: (Alex, Erik) (Bob, Frank) (Charles, Devin) Result of verification function: true Submission In addition to your response for the Theory section and your code for the Implementation section, you will need to create a README.md file defining how to run your program. If you are using Java / C++, include instructions for both the compilation command (javac or g++, for example) and the run command (java or ./a.out, for example). If you are using Python or JavaScript, then include the appropriate run commands (node or python, for example). Lastly, include instructions for where to place any additional input files