\problemdata     
{computation-4}           
{stable marriage algorithm}              
{}              
{S02 in-class Week 5} 		
{S02 Meyer}        	




\begin{problem}
The table below shows the preferences of each girl and boy in decreasing
order.

\begin{eqnarray*}
boys & \quad & girls \\
1 : C B E A D & \quad & A : 3 5 2 1 4 \\
2 : A B E C D & \quad & B : 5 2 1 4 3 \\
3 : D C B A E & \quad & C : 4 3 5 1 2 \\
4 : A C D B E & \quad & D : 1 2 3 4 5 \\
5 : A B D E C & \quad & E : 2 3 4 1 5
\end{eqnarray*}

\bparts

\ppart We saw that using a ``boy greedy'' strategy, where each boy in turn
got his favorite available girl led to marriages in which Boy 4 and Girl C
are a rogue couple.  Which other boys are in rogue couples in these
marriages?  (You should reconstruct the greedy marriages from the table.)

\solution{
The boy greedy marriages were:

\begin{eqnarray*}
1 \rightarrow C \\
2 \rightarrow A \\
3 \rightarrow D \\
4 \rightarrow B \\
5 \rightarrow E \\
\end{eqnarray*}

Boy 5 and Girl B are a rogue couple; so are Boy 5 and Girl A.

But Boys 1, 2, and 3 all got their top pick among the girls; none would
even think of running off.
}

\ppart Find a stable set of marriages.  (You can do this by trial and
error; you're not expected to remember the Mating Procedure which we'll
review in a little while.)

\solution{Since all girls have different first choices, a ``girl greedy'' strategy
will immediately instantly lead to stable marriages.  The Mating algorithm
yields another set.
\begin{eqnarray*}
1 \rightarrow E \\
2 \rightarrow B \\
3 \rightarrow D \\
4 \rightarrow C \\
5 \rightarrow A \\
\end{eqnarray*}
}
\eparts
\end{problem}

