CS 2223 D Term 2009

Computer Science Department

CS2223 Algorithms
Homework 1 - D Term 2009

PROF. CAROLINA RUIZ

Due Date: March 24, 2009 at 12:30 (code) and 1:00 (report) PM
See course policy regarding late homework submissions

Homework Instructions:
- Read Chapter 1 of the textbook in detail.
- This is an individual homework. No collaboration is allowed.
- Submission Instructions:
  1. Code Submission: To submit, login to a CCC unix machine. If the files that you plan to submit are not already in a directory on your CCC Unix account, transfer them there first. Then use the following command to submit your files:
    /cs/bin/turnin submit cs2223 hw1 yourfile1 yourfile2 ... yourfilen
    replace yourfile1 yourfile2 ... yourfilen with the actual list of files you want to submit. Include a README.txt file providing information on what files are contained in your submission, what each one contains, and how to run your program.
    We suggest that you test the submission process AS SOON AS POSSIBLE by creating a text file named JustATest.txt and submitting it using turnin:
    /cs/bin/turnin submit cs2223 hw1 JustATest.txt
    See Using the turnin Program for more information and help.
  2. Written Homework: Submit a hardcopy of your written homework solutions to Problems 2, 3, and 4 by the beginning of class (i.e., 1:00 pm) on Tuesday, March 24th. 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 Java (or C or C++) program satisfying ALL the specifications below:
- (100 points) Your program should faithfully implement Gale's and Shapley's propose-reject algorithm on page 6 of your textbook.
- (60 points) Your program should use the efficient implementation described in the Textbook Chapter 1 Slides (see slides 15 and 16).
- (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 tables 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 tables.
- (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.
- (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	1st	2nd	3rd	4th	5th
Man 1	1	3	5	4	2
Man 2	4	2	5	3	1
Man 3	3	5	1	2	4
Man 4	4	2	5	3	1
Man 5	1	2	3	4	5

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

(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 are no instabilities in that output.
(40 points) Using the verbose mode of your code, include in your homework solutions the first 10 iterations 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. If not, explain clearly why it is unstable.
```
Man (husband): M1  M2  M3  M4  M5
Woman  (wife): W5  W3  W2  W1  W4
```
(70 points) Problem 4. Run your program in non-verbose mode 10 times, each time with one of the values of n below:
```
n= 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000
```
where the preference lists for all the n men are the same:
```
Wn, W(n-1), W(n-2), ...., W3, W2, W1. 
```
that is, all the men prefer woman n the most and woman 1 the least; and the preference lists for all the n women are the same:
```
M1, M2, M3, ....., M(n-2), M(n-1), Mn
```
that is, all the women prefer man 1 the most and man n the least.
- (40 points) Run your program on each of these 10 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 graph 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 n= 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000. Describe any observations you can make about this graph.

CS2223 Algorithms Homework 1 - D Term 2009

PROF. CAROLINA RUIZ

CS2223 Algorithms
Homework 1 - D Term 2009