\problemdata     
{computation-5}           
{Mating algorithm}              
{}              
{S02 in-class Week 5} 		
{S02 Meyer}        	


\begin{problem} Four Students want separate assignments to four VI-A
Companies.  Here are their preference rankings:
\begin{center}
\begin{tabular}{c|c} 
Student & Companies \\ \hline
Albert:  & Compaq, Bellcore, AT\&T, Draper \\
Carole:     & AT\&T, Bellcore, Draper, Compaq \\
Eric:   & Compaq, Draper, AT\&T, Bellcore \\
Radhi:    & Draper, AT\&T, Bellcore, Compaq 
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{c|c}
Company   & Students \\ \hline
AT\&T:    & Radhi, Albert, Eric, Carole \\
Bellcore: & Eric, Carole, Albert, Radhi \\
Compaq:   & Radhi, Eric, Albert, Carole \\
Draper:   & Carole, Radhi, Eric, Albert
\end{tabular}
\end{center}
Use the Mating Algorithm to find \emph{two} stable assignments of Students
to Companies.

\solution{Treat Students as Boys and the result is the following
assignment:
\begin{center}
\begin{tabular}{c|c|c} 
Student & Companies & Rank in the original list \\ \hline
Albert:  & Bellcore & 2\\
Carole:     & AT\&T & 1\\
Eric:   & Compaq & 1\\
Radhi:    & Draper &1
\end{tabular}
\end{center}

Treat Companies as Boys and the result is the following assignment:
\begin{center}
\begin{tabular}{c|c|c}
Company & Students & Rank in the original list\\ \hline
AT\&T:    & Albert & 2\\
Bellcore: & Carole & 2\\
Compaq:   & Eric & 2\\
Draper:   & Radhi & 2
\end{tabular}
\end{center}
}
\end{problem}