This program is an implementation of the standard Stable Marriage problem, written by Chuck Connell in December 2007, for COMP 160 Algorithms at Tufts University. To Run the Program ------------------ Log onto sun.cs.tufts.edu Make sure StableMarriage.class and the test input files (stable*.txt) are in the current directory. Type: use jdk1.4.2 Type: java StableMarriage Example: java StableMarriage stable10.txt To Compile the Program ---------------------- Log onto sun.cs.tufts.edu Make sure StableMarriage.java is in the current directory. Type: use jdk1.4.2 Type: javac StableMarriage.java Input Files ----------- Each input file contains one instance of the stable marriage problem -- a list of men and women, with their preference rankings for each other. The format of an input file is simple and documented within the file, making it easy to create new input cases. Background about the Stable Marriage Problem (SMP) -------------------------------------------------- The Stable Marriage problem is to match a set of men and women with each other, so that no two pairings are "unstable". Unstable pairings are those in which the man of Pair A prefers the woman of Pair B, and the woman of Pair B prefers the man of Pair A. The input to SMP is: for each man, an ordered list of his preferences for the women; for each woman, an ordered list of her preferences for the men. The number of men and women is equal. SMP is interesting because it applies to many more situations than fictitious marriages. The most well-know of these is the problem of matching medical students with training slots at hospitals. I have implemented the Gale-Shapley (GS) algorithm from 1962, which is the standard solution for SMP. While I do not address them here, there are also many variations of standard SMP, including stable roommates (where there is a single set of people to match with each other), preference ties (where some men and women give equal rank to potential mates), and married medical students (where couples who are already married must be assigned to the same hospital). Time Complexity of GS --------------------- During our class discussion about SMP, there was some confusion about whether GS has a worst-case running time of O(n^2) or O(n^3). I confirmed that it is O(n^2). I did this in several ways: I inspected the pseudo-code for GS found on the Internet, I inspected my implementation of this algorithm, and I inserted counters into my code that report the number of iterations of key loops. I also contact David Manlove at Glasgow University, who is one of the world's experts on this problem. He confirmed to me that GS is O(n^2) and that the SMP problem is Omega(n^2). So both SMP and the GS algorithm are Theta(n^2); no significantly faster algorithm is possible. Space Complexity of My Implementation ------------------------------------- Let N be the number of men in an instance of SMP. The size of the main data structures (ManPrefers and WomanPrefers) is each N^2. There are three important supporting data structures that are each size N -- ManIsEngagedTo, WomanIsEngagedTo, and ProposalRank. The latter two may not be strictly required but, as a set, they are very helpful for program readability and execution speed. How they help with speed is explained below. Main Features of this Implementation ------------------------------------ One principle I followed is to use clear, descriptive variable names. Except for a couple loop counters, every variable name is a meaningful description of what that variable does. My goal is for the code to be readable by someone just learning this algorithm. Toward the same aim, I also included generous comments throughout the code explain clearly what each line does and how it relates to the overall algorithm. While my comments and variable names may be long-winded, I also worked to write code that is as tight and fast as possible. In particular, the following annotated areas of the source code show this: #1 -- The three supporting data structures are initialized here. Only the first (ManIsEngagedTo) is strictly required, since the others could be derived during runtime. But those arrays, WomanIsEngagedTo and ProposalRank, allow very fast index lookup of important information later. #2 -- This line uses triple array indexing to find the next woman that the current man should propose to, in one step. It is possible to code this section as another loop, searching for the next woman in the man's preference list, but my implementation is faster. Reading from the inside out, ThisMan is the number of the man currently proposing. ProposalRank[ThisMan] finds how far along his proposal list this man is. That number is used with ManPrefers[ThisMan] to find the woman at that position in the man's preference list. #3 -- This is one area of the code that MIGHT be amenable to speed improvement. This section looks through a woman's preferences to see whether she prefers the man proposing to her, or a man she is already engaged to. I tried to find a way to make this section a direct array lookup of some kind, instead of a short loop, but could not see a way to do that. It is important to note however, that this loop does not make the algorithm N^3, even though it is embedded within an N^2 loop. The reason is that it can never happen that each of the (possibly) N^2 men proposing requires N lookups within a woman's preference list. First, if the woman is not engaged, there is no lookup in her preference list. Second, it cannot be the case that every person marries the last person on his/her list; the worst outcome is that everyone gets a choice in the middle of their list. #4 -- Here we use the array WomanIsEngagedTo to cancel a man's previous engagement in one step. Without this optional array, some searching would be required to find the man whose engagement was just broken. What I Learned -------------- I learned about this entire problem and its variations, since I did not know about it at all. I learned much more about Java, since I had used this language only lightly. I learned the NetBeans development environment, which is very nice. I learned that relatively small extra space usage can improve execution speed, and have a large impact on readability. (Although I already knew this to some extent, since I have been programming for a long time.) Links for More Information -------------------------- http://www1.cs.columbia.edu/~evs/intro/stable/writeup.html (non-technical introduction) http://en.wikipedia.org/wiki/Stable_marriage_problem (encyclopedia article) http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=7676 (thorough treatment) http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html (Java online matching program) http://www.dcs.gla.ac.uk/research/algorithms/stable/#soft (source code for various implementations of GS and variations of SMP) http://www.dcs.gla.ac.uk/~davidm/ (David Manlove, Glasgow University) Contact Information ------------------- Chuck Connell Woburn, MA www.chc-3.com connell@chc-3.com