Assignment 1: Perfect Marriage in King Arthur’s court Solution

King Arthur issues a decree: all the knights and ladies must marry. As it happens, there are an equal number, so he insists this should be possible. Arthur orders Merlin, the magician, to come up with an algorithm to match the knights and ladies up so that no marriage is unstable. Merlin comes up with an algorithm:

• Every knight ranks the ladies in order of preference.

• Similarly, every lady ranks the knights in order of preference.

• Each knight proposes to the lady he prefers most.

• Then, each lady either considers all the proposals she has received, and replies “maybe” to the knight she likes best (of the ones that proposed to her) and “no” to all the rest. Thus, she is now engaged to that knight.

• As long as there are unengaged knights, each unengaged knight proposes to the most-preferred lady to whom he has not yet proposed, regardless of whether or not she is engaged.

• Each lady reviews the new proposals, and either replies “maybe” if she is not yet engaged or if she prefers this knight to the one she was previously engaged to (if she rejects her previous knight, he becomes unengaged)

Merlin proves to King Arthur that as long as there are the same number of knights and ladies, this algorithm will result in a perfect, stable marriage: everyone will be married, and there will not exist some knight and some lady who would both rather be with each other than with their current partner.

We discussed this algorithm, called Gale-Shapley, and proved that its asymptotic complexity is O(n2), as well as that the algorithm provides a stable marriage. In most future assignments, you will have to spend some time proving complexity bounds, but for this one, you will not. Instead, you will:

• Implement Gale-Shapley in Python.

• Document the invariants in your code

1

• Benchmark your implementation on data sets of different sizes, which we provide

• Plot the running time versus the input size, and explain whether or not the results meet your expectations.

You will need to upload your code (python file) as well as the

Data File Format and Program Arguments

It is essential to understand that you are writing software whose output will be consumed by other software (namely, the autograder). Thus, your output must conform exactly to the specification given here, just as we promise the input files we give you will conform exactly to the input specification we give.

Your program must be called marriage.py and must take a single command-line argument, which specifies an input file.

Failure to adhere to these specifications will result in a zero grade for Functional Correctness.

We provide a zip archive on Sakai, marriage.zip, containing input files on which you are to benchmark your program as described below. We will, in addition, test your program on other inputs that we do not provide you.

Input Specification

We provide an ASCII (8-bit) text file. The first line contains only a single integer, which may be multiple digits. That is the value of n: it is the number of men (which is also the number of women). Every subsequent line contains n + 1 entries, separated by a space. For the first n lines after this first line, the first entry on each line is the name of a knight, and the rest of the entries are his order of preference for the ladies (we are only using a single name for each person, rather than first and last names, and there must be no duplicates). For the next n lines, the first entry on each line is the name of a lady, and the rest of the entries are her order of preference for the knights. Names may contain alphanumeric characters (they may look like real human names, or they may not).

Example:

2

Galahad Guinevere Elaine

Lancelot Guinevere Elaine

Elaine Galahad Lancelot

Guinevere Lancelot Galahad

2

Output Specification

You provide output on STDOUT. It must contain n lines, one per marriage. Each line has the knight’s name, then a space, then the lady’s name. We do not specify the order of the knights; we will sort your input and the correct answer in order to compare them.

Example:

Galahad Elaine

Lancelot Guinevere

If no input file is provided, or if the input format is not exactly as specified above, your program must exit with result code 1, and should print nothing on STDOUT. In python, this is achieved with

exit(1)

You must not return any other output on STDOUT. How, then, can you easily benchmark your program? We suggest one of two ways:

• On Linux or Mac OS X, use the time command to run your code from the command line.

• On any operating system, use the timeit module in Python. You can wrap the main body of your program in a call to timeit.timeit and then report the resulting time on STDERR.

If you do not understand what we mean by STDOUT and STDERR, please ask the course staff.

Pair Programming

You will work with a partner for this entire assignment. Please refer to the pair programming policy in the syllabus. For this first assignment, we have assigned partners. For future assignments, you may choose your partner.

Lateness

Submissions will not be accepted after the due date, except with the intervention of the Dean’s Office in the case of serious medical, family, or other personal crises.

3

Grading Rubric

Your grade will be based on four components:

• Functional Correctness (25%)

• Design and Representation (25%)

• Invariant Documentation (25%)

• Benchmarking and Analysis (25%)

Of these, only Functional Correctness will be autograded. Note that we are asking you to practice defensive programming: if you receive bad input, your program must exit with error code 1. We reserve the right to test your code with bad inputs. The idea here is that it is important not only to give the right answer with good inputs, but to not silently give the wrong answer with bad inputs. Doing so leads to insecure software.

Design and Representation is our evaluation of the structure of your program, the choice of representations (how do you represent a knight, for example? How do you represent a preference list?), and the use of appropriate (not excessive) comments. We will be relatively lenient in the Design and Representation grade on this first assignment, and progressively more demanding over the course of the semester.

Invariant Documentation is to force you to reason about the running time of the algorithm, as well as its correctness. Whenever you have a loop in the body of your algorithm, you should state whatever invariants hold. Consider what we discussed in class: Initialization, Maintenance, and Termination. So, at present, this shows up in the form of comments within your source code.

Benchmarking and Analysis will be relatively simple in this assignment. You should include a PDF in your upload to Gradescope, along with your program.

We provide you with four data files, each with a different value for n. The sizes are: 10, 100, 1000, and 5000 knights. You must time three runs on each of those inputs, and compute the mean (average) time for each input. Then, plot those times against the input size. You may use any plotting tool you like; Excel is fine. Submit a PDF to Gradescope with your plot, as well as an explanation of what you see. Does your plot bear out the O(n2) asymptotic complexity of Gale-Shapley? Why or why not? If not, can you come up with any explanation?

Tips and Pitfalls

• It’s possible for a knight and a lady to have the same name. Your imple-mentation must handle this.

• Be sure to have the knights propose first; if you have the ladies propose to the knights first, you will still end up with a stable marriage but it won’t be the one expected by the autograder!

4

• Don’t overcomplicate this assignment. My solution is 75 lines of code and involves no classes. I’ve seen solutions with a Knight class, Lady class, Proposal class, Marriage class. . . all for this one problem. Don’t make more work for yourself.