COSC 511 HW0909  due: 9/11/13 


Suppose there are two disjoint sets. M = m1, m2, m3 and W = w1, w2, w3.
The elements of M have the following preferences from highest to lowest:
<table>
m1: w1, w2, w3
m2: w1, w2, w3
m3: w2, w1, w3

The elements of W have the following preferences from highest to lowest:
w1: m3, m2, m1
w2: m3, m2, m1
w3: m1, m3, m2

A random number generator returns the following sequence:
1, 1, 2, 1, 3, 2, 3, 3, 1, 2, 1, 1, 2, 1, 3, 2, 3, 3, 1, 2, ...

1. What is the result of the Gale Shipley algorithm if the order of m<sub>i</sub>
is given by the random number sequence?

2. Over the course of the execution, how many different w<sub>i</sub> is m<sub>1</sub> engaged to?

3. After the execution completes, how many total engagements have occurred?

4. Suppose the random number generator returns the following sequence:
1, 2, 3, 1, 2, 3, 1, 2, 3, ... (repeat)

4.a. What is the result of the Gale Shipley algorithm with the new sequence?

4.b. Is this the same matching as for #1?


5. For the matching obtained in #4, who is 'happier' -- the group of m<sub>i</sub> 
or the group of w<sub>i</sub>


6. Using the random number sequence given in #4, suppose the elements of W are the
one doing the proposing. What is the result?