\problemdata                                                             
        {Stable Marriage - Students/Companies} % latex-friendly label for the prob.
        {Stable Marriage Process} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 5,1} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Four people are interested in participating in
the VI-A program where each person ranks his top choices of companies
and the companies rank the students as well.  The people Albert, Ben,
Chris, and Doug are interested in companies AT\&T, Bellcore, Compaq,
and Draper Labs.  Below are the students' rankings of the companies
and the companies' rankings of the students.

\begin{center}
\begin{tabular}{c|c} 
Student & Companies \\ \hline
Albert:  & Compaq, Bellcore, AT\&T, Draper \\
Ben:     & AT\&T, Bellcore, Draper, Compaq \\
Chris:   & Compaq, Draper, AT\&T, Bellcore \\
Doug:    & Draper, AT\&T, Bellcore, Compaq 
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{c|c}
Company & Students \\ \hline
AT\&T:    & Doug, Albert, Chris, Ben \\
Bellcore: & Chris, Ben, Albert, Doug \\
Compaq:   & Doug, Chris, Albert, Ben \\
Draper:   & Ben, Doug, Chris, Albert
\end{tabular}
\end{center}

\begin{problemparts}
\problempart What is a student-optimal stable marriage set for
this problem?

\solution{
You were guaranteed to get a student-optimal stable marriage set if
you ran the stable marriage algorithm given in lecture, where Students
are Men and Companies are Women.  The result is the following assignment:

\begin{center}
\begin{tabular}{c|c|c} 
Student & Companies & Rank in the original list \\ \hline
Albert:  & Bellcore & 2\\
Ben:     & AT\&T & 1\\
Chris:   & Compaq & 1\\
Doug:    & Draper &1
\end{tabular}
\end{center}
}

\problempart What is a company-optimal stable marriage set for
this problem?

\solution{
Similarly, you were guaranteed to get a company-optimal stable
marriage set if you ran the stable marriage algorithm given in
lecture, where Students are Women and Companies are Men.  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: & Ben & 2\\
Compaq:   & Chris & 2\\
Draper:   & Doug & 2
\end{tabular}
\end{center}
}

\end{problemparts}
\end{problem}                                 