CS 2223 B Term 2013

Computer Science Department

CS2223 Algorithms
Homework 1 - B Term 2013

PROF. CAROLINA RUIZ

Due Date: Tuesday Nov. 5th, 2013 at 1:00 PM code, and 2:00 PM report
See course policy regarding late homework submissions

Homework Instructions:
- This is an individual homework. No collaboration is allowed.
- Submission Instructions:
  1. Code Submission: Submit your Python code (Problem 1 below) by 1:00 pm on Tuesday, Nov. 5th 2013 using the Blackboard site for CS2223 available from myWPI. Login to myWPI, go to CS2223 under "My Courses", then go to "Assignments", and submit your homework under "HW1".
  2. Written Homework: Submit a hardcopy of your written homework solutions to Problems 2, 3, and 4 by the beginning of class (i.e., by 2:00 pm) on Tuesday, Nov. 5th 2013. Remember to show your work and explain your answers.
- See the course webpage for the late homework submission policy.

Problems:

(250 points) Problem 1. Write a Python program satisfying ALL the specifications below:
- (100 points) Your program should faithfully implement Gale's and Shapley's propose-reject algorithm discussed in class. This algorithm is provided on Slide 9 of the slides that accompany Jon Kleinberg's and Éva Tardos' Algorithm Design textbook. (The algorithm is also available on page 6 in Chapter 1 of the aforementioned book). These resources are available from Prof. Kevin Wayne's Algorithms Course Webpage at Princeton University:
- (60 points) Your program MUST use the efficient implementation described in the above slides. See slides 14 and 15. However, the list of preferences for men (and for women) should be represented as a list of lists, as described below. For your convenience, we list below the data structures that you must use:
  - n: number of men which is equal to the number of women
  - menPreferences: list of lists as illustrated below
  - womenPreferences: list of lists as illustrated below
  - FreeMen: stack of free men as illustrated below
  - wife: a Python list where wife[m] = w, if m and w are currently matched (set wife[m] = -1 if m is currently free)
  - husband: a Python list where husband[w] = m, if m and w are currently matched (set husband[w] = -1 if w is currently free)
  - ordinal (what is called "inverse" in the slides): A list of lists with the ordinal position of each men in a woman's preference list. See illustration below
  - As specified on the Slides, "For each man, maintain a pointer to woman in list for next proposal." For this, you can use a list MenNextProposal of length n (initially equal to [0,0, ...0]) where MenNextProposal[m] contains the position on his preference list that he'll use for his next proposal. That is, he'll propose next (if needed) to the woman contained in menPreferences[m][MenNextProposal[m]].
  DON'T use objects or fancier data structures than the lists (= arrays) and variables above. You are REQUIRED to use the simple lists and stack as described above since the detailed time analysis of the algorithm that we'll perform in class depend on them.
  Note that the wife list (and also the husband list) keeps track of the matching that the algorithm constructs. Hence, there is no need for an additional data structure to store the stable matching.
  Note that in contrast with the notation used in these slides, Python indexes lists and arrays starting at 0 (not at 1). So in this homework we'll index men and women starting at 0. Hence, a man's favorite woman would be his 0th preference (not his 1st preference!).
  For illustration purposes, the Python structures that will represent the preferences for men and for women for the example provided in Problem 2 below are:
```
menPreferences = [[0, 2, 4, 3, 1], [3, 1, 4, 2, 0], [2, 4, 0, 1, 3], [3, 1, 4, 2, 0], [0, 1, 2, 3, 4]]

womenPreferences = [[1, 2, 3, 4, 0], [2, 3, 4, 0, 1], [3, 4, 0, 1, 2], [4, 0, 1, 2, 3], [0, 1, 2, 3, 4]]
```
  With this representation, the ith preferred woman of man j can be found at
```
menPreferences[j][i]
```
  For instance, man 1's favorite woman is woman 3 since:
```
menPreferences[1][0] is equal to 3.
```
  The stack of free men would be initially be:
```
FreeMen = [n-1, n-2, ..., 2, 1, 0]
```
  See http://docs.python.org/2/tutorial/datastructures.html for a description of how a list can be used as a stack in Python.
  Finally, the list of lists ordinal for this example will be:
```
ordinal = [[4, 0, 1, 2, 3], [3, 4, 0, 1, 2], [2, 3, 4, 0, 1], [1, 2, 3, 4, 0], [0, 1, 2, 3, 4]]
```
  So woman 2 prefers man 3 over man 1 since ordinal[2][3] < ordinal[2][1]. Note that ordinal[2][3] == 0 0th preference) and ordinal[2][1] == 3 (3rd preference).
- (20 points) For simplicity, we suggest that instead of your program reading its input, you include the value n (= number of men = number of women) and data structures containing the preference lists of men and women with the values you need on each run hardwired in your code. You can comment out those preference tables when you need to run your program with a different n and/or different preference lists.
- (10 points) Your program should print the final matching it constructs in an easy to read and understand format.
- (30 points) Your program should have a verbose and a non-verbose options. The verbose option prints who proposes to whom on each iteration of the loop and whether the woman accepts (if she was already engaged, print to which man) or rejects the proposal, in an easy to read and understand format. Your program should read whether to run verbose or non-verbose as an input. Choose a simple convention for this input value and explain it in your homework solutions so that we know how to run your program. Preferably, provide a command line option "-v" for verbose and "-nv" for non-verbose.
- (30 points) Your program should use the internal clock to measure the execution time of your program. You should start the clock right before the beginning of the while-loop (after you have initialized all the data structures) and should stop the clock right after the end of the while-loop (before printing out the matching).
  The total execution time should be printed by your program both in verbose and non-verbose modes.

(100 points) Problem 2. Run your program with the following example. Here, we will follow the notation suggested in the efficient implementation above. n=5.

Men's preferences	0th	1st	2nd	3rd	4th
Man 0	0	2	4	3	1
Man 1	3	1	4	2	0
Man 2	2	4	0	1	3
Man 3	3	1	4	2	0
Man 4	0	1	2	3	4

Women's preferences	0th	1st	2nd	3rd	4th
Woman 0	1	2	3	4	0
Woman 1	2	3	4	0	1
Woman 2	3	4	0	1	2
Woman 3	4	0	1	2	3
Woman 4	0	1	2	3	4

(30 points) Include in your homework solutions easy-to-follow instructions so that we can quickly run your program with this example. You should leave the data structures with the preference list values above in your code, commented out if necessary.
(30 points) Include in your homework solutions the stable matching that your program outputs. Relying on the preference tables, provide a decisive argument proving that this output is indeed a stable matching (saying that it is stable because is the output of your program is not a decisive argument!). That is, show that there is no man M and woman W, not married to each other, who prefer each other over their assigned spouses.
(40 points) Using the verbose mode of your code, include in your homework solutions the first 10 iterations (or the total number of iterations if your program takes less than 10 iterations to complete) of the propose-reject loop. For each of these 10 iterations (4 points each), add by hand clear explanations of how the proposing man was chosen, how he decided whom to propose to, and why his proposal was accepted or rejected.

(30 points) Problem 3. Is the following matching stable with respect to the tables of preferences of the 5 men and 5 women in Problem 2 above? If yes, provide a decisive argument to prove it. (That is, prove that there is no man M and woman W, not married to each other, who prefer each other over their assigned spouses.) If not, explain clearly why it is unstable. (That is, show that there is a man M and a woman W, not married to each other, who prefer each other over their assigned spouses.)
```
Man (husband): M0  M1  M2  M3  M4
Woman  (wife): W4  W2  W1  W0  W3
```
(70 points) Problem 4. Run your program in non-verbose mode 7 times, each time with one of the values of n below:
```
n= 10, 100, 1000, 2000, 3000, 4000, 5000. 
```
where the preference lists for all the n men are the same (generate these preference lists within your Python code):
```
W0, W1, W2, ....., W(n-2), W(n-1)
```
that is, all the men prefer woman 0 the most and woman n-1 the least; and the preference lists for all the n women are the same:
```
M(n-1), M(n-2), ...., M2, M1, M0. 
```
that is, all the women prefer man n-1 the most and man 0 the least.
- (40 points) Run your program on each of these 7 cases in non-verbose mode. Record in your homework solutions the execution time taken by your program to find the stable matching for each of these values of n. For n=100, include in your homework solutions also the output stable matching (just for n=100 to save space).
- (30 points) Plot a curve where the x axis correspond to n (= number of men = number of women), and the y axis is the time taken by your program to find the stable matching for each value of n= 10, 100, 1000, 2000, 3000, 4000, 5000. Describe any observations you can make about this plot.

CS2223 Algorithms Homework 1 - B Term 2013

PROF. CAROLINA RUIZ

CS2223 Algorithms
Homework 1 - B Term 2013