CSE 373: Data Structures and Algorithms, Winter 2013

Homework 1 (Stable Marriage) FAQ

Q: What are some good resources I can look at to help me on this assignment?

A: The lecture programs/slides, section handout, or textbook are always good places to look.

Q: I'm stuck! How can I get help on the assignment?

A: We will be happy to help you. Try posting on the course message forum (but don't attach/paste your solution code, please), or come see us during our TA/instructor office hours.

Q: I am trying to use Eclipse, but it won't compile my program. It says something about an "Ant Build".

A: You need to put your files into a Project. Don't just open them with "File / Open..."

Q: How do I get Eclipse to find the source files and input files for the project?

A: Put the input *.txt files in your project's root folder, and put source code files in the src/ subdirectory of your project. After adding any files to the directory of an already-existing project, you must right-click the project in the Eclipse Project Explorer pane and choose Refresh to see them.

Q: I put files in my Eclipse project folder, but it does not show those files in Eclipse. Where are they?

A: After adding any files to the directory of an already-existing project, you must right-click the project in the Eclipse Project Explorer pane and choose Refresh to see them.

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 spec, 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: The provided algorithm pseudo-code says that the man should "remove" his most-preferred woman. Does this mean I should literally remove her from my data collection?

A: It depends on your implementation and what collections you are using. In our own instructor solution, yes, we literally do remove the woman from that man's collection of women to consider. An alternative would be to just remember that she has already been considered by that man, such as with a counter or index. You are not required to literally remove the woman from your data, so long as you stop considering that woman for a potential match with that man in future rounds.

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 kind of collections should I use? If I use a map, what keys and values should it store?

A: The spec has many guidelines you can use to help decide what collections to use. If you use a map, you will often end up looking for information using a person's name as a key.

Q: I am writing a Person class. My code uses a map with Person objects as the keys. But I don't know how to look up anything in the map. If I want to get something out, I have to pass a Person as a key. Where do I get that Person object key from? Do I just create a dummy temporary object to use as a key?

A: It's fine to write a Person class, but we strongly recommend that you do not make a Map<Person, ???> in your code, for precisely this reason. Maps are all about having a piece of information that you have (the key), and a piece that you want (the value). In the situation being described here, you don't really have the Person, so they shouldn't be the key. There are also some issues that can come up, such as, if Persons are keys in a TreeMap they must be Comparable, and if they are keys in a HashMap they ought to have a hashCode method, which we have not talked about in class yet.

Consider using their name (a String) as the key instead. If you do want to look up a Person object, you can always make another map from names to the corresponding Person object that uses that name.

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

A: When addPerson is called, the gender is passed. You can remember this information in your MatchMaker object in some kind of collection.

Q: Why does my code think every person is a man (or woman)? Why can't my code ever find the person whose name I am searching for?

A: You might be comparing strings using the == operator. You must use the .equals method.

Q: I want to add another method to MatchMaker that is not listed in the spec. Is that okay?

A: Yes.

Q: I want to change the provided Main.java. Is that okay?

A: No. Your code must work with the provided main program, unmodified.

Q: I want to change one of the specified methods of MatchMaker to add a parameter, change its return type, etc. Is that okay?

A: No.

Q: My output is similar to the provided output, but not exactly the same. Will I lose points?

A: Yes. Yours must match EXACTLY, including capitalization, blank lines, spacing, everything. To the character. We are super picky. Use the Output Comparison Tool to verify that your output matches exactly.

Q: Will my solution get full credit? Is it written in the style you want? Are my methods okay? Is this the collection you want me to use? Will I get marked off for this code?

A: We call this "pre-grading," and we don't want to answer questions at that high level of detail. We feel that you should be able to figure out the answers to such things yourself by looking at the spec and online guidelines and by using your best judgment. The TA won't look over your entire program for mistakes or tell you exactly what things you will get marked off for. We'll grade you on the guidelines in the homework document, and we can help you with specific issues but cannot evaluate your entire program or directly confirm whether various parts of your code will or won't lose points.

Q: How many lines long should my solution be? If my solution has a lot more/fewer lines than that, will I be marked off?

A: Our instructor solution is around 110 lines long including comments. But that is just for reference; you don't have to exactly match our program's length. We're just mentioning it as a sanity check. If your numbers are WAY off from ours (like, say, by a factor of 2), you may be solving the problem in the wrong way. But please don't needlessly hack at your code just to reduce/increase its line count to try to match ours.