Homework 3 (MatchMaker) FAQ

Q: How does the algorithm work? What algorithm should I use, how do I make a stable marriage ?

A: The method of creating a Stable Marriage is known as the Gale Shapley algorithm. The pseudo-code for this algorithm is provided on the assignment write-up, it also gives an example of the finding of a stable marriage following this algorithm. Every round each unpaired man will propose to their highest ranked potential wife to whom they have not yet proposed. If she is single, or prefers the man making the proposal more than her husband she becomes married to that man (divorcing her husband if she is married). This continues until a round brings no further changes, at which point the marriages are considered stable. For more information on the Stable Marriage problem see its Wikipedia Article.

Q: When do I know that I have reached the end of the rounds, how do I know if the marriages are stable?

A: For this assignment the state of the marriages is considered stable if, during the last round, no changes were made.

Q: What map should I use, what keys and values should it store?

A: The write-up states that "... each MatchMaker should maintain a map from names to Person objects ..." - this is to facilitate the use of names to refer to people, rather than direct links to their Person objects. Many methods of Person that you use will give you the String for another person's name, with which you will need access to that other Person object, to this end you will use your map.

Q: How do I tell if a person is a man or a woman?

A: The Person class does not contain the ability to tell a man from a woman, the only time you are given the men and the woman (or rather the first and the second groups) is in your constructor. If you wish to know to which group a person belongs you must keep track of the groups in which they were originally sent.

Q: What should my initial round be?

A: Your round should start at 0 when your object is initialized, a call to getRound before any calls to nextMatchRound should return 0 (the write-up incorrectly states that "... When a MatchMaker is first created, it is on round 1 ...").

Q: How do I know what order my map or set is storing the elements?

A: The way elements are stored in a set or a map is determined by the implementation that is used for that Set<E> or Map<K, V> interface. Generally, for such data structures the order values are stored or retrieved is not important (as opposed to an array, list, or stack/queue), but for this assignment, certain implementations will give the correct output and others will not. The implementations to which you have been introduced for Set<E> are HashSet<E> and TreeSet<E> (maintains sorted order), and for Map<K, V> are HashMap<K, V> and TreeMap<K, V> (maintains sorted order). Keep in mind that sets and maps (generic) are also given to you as parameters or return values to and from method calls.

Q: How can my toString return more than one line?

A: A single String can store more than one line of code by use of the new line escape sequence for Java, "\n". When this symbol appears in a String it is equivalent to a new line.