\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\def\bparts{\begin{problemparts}}
\def\eparts{\end{problemparts}}
\def\ppart{\problempart}

\begin{document} 
\inclassproblems{5, Wed}                    % !! start the paper

%% source: Fall99 Q2, prob 4
%% topics: {Graphs, Trees, State Machines, Counting, Well-order}

\begin{problem}
We apply the following operation to a simple graph $G$:
pick two vertices $u \neq v$ such that either
\begin{enumerate}
\item there is an edge of $G$ between $u$ and $v$ and there is also a path
from $u$ to $v$ which does \emph{not} include this edge; in this case,
delete the edge $\set{u,v}$.

\item there is no path from $u$ to $v$; in this case, add the edge
$\set{u,v}$.
\end{enumerate}

Keep repeating these operations until it is no longer possible to find two
vertices $u \neq v$ to which an operation applies.

Assume the vertices of $G$ are the integers $1,2,\dots,n$ for some $n \geq
2$.  This procedure can be modelled as a state machine whose states are
all possible simple graphs with vertices $1,2,\dots,n$.  $G$ is the start
state, and the final states are the graphs on which no operation is
possible.

\bparts

\ppart Let $G$ be the graph with vertices $\set{1,2,3,4}$ and edges
\[
\set{\set{1,2},\set{3,4}}
\]
What are the possible final states reachable from start state $G$?  Draw
them.

\solution{It's not possible to delete any edge.  The procedure can only
add an edge connecting exactly one of vertices 1 or 2 to exactly one of
vertices 3 or 4, and then terminate.  So there are four possible final
states}

\ppart \label{derived} Below are three derived variables.  Indicate the
\emph{strongest} property from the list below that each variable is
guaranteed to satisfy, no matter what the starting graph $G$ is, and
justify your answer.  The properties are: \emph{constant}, \emph{strictly
increasing}, \emph{strictly decreasing} ,\emph{weakly increasing},
\emph{weakly decreasing}, \emph{none of these}

For any state, let $e$ be the number of edges in it, and let $c$ be the
number of connected components it has.  For example, since $e$ may
increase or decrease in a transition, it does not have any of the first
four properties, so it would be classified \emph{none of these}.  The
derived variables are
\begin{enumerate}

\item[i)] $c$, \solution{weakly decreasing}
\item[ii)] $c+e$, \solution{weakly decreasing}
\item[iii)] $2c+e$. \solution{strictly decreasing}

\end{enumerate}

\ppart Conclude that the procedure terminates.

\solution{Because the derived variable iii) is a natural-number valued
variable and is decreasing.

To show that the variable iii) decreases, note that the rule for deleting
an edge ensures that the connectedness relation does not change, so
neither does the number of connected components; therefore the variable
decreases by one when an edge is deleted.  The rule for adding an edge
ensures that the number of connected components decreases by one, so the
variable changes by $-2$ for the reduced number of components and $+1$ for
the added edge, for a net decrease of 1.}

\ppart Prove that any final state must be a 
tree on the vertices.

\solution{We use the characterization of a tree as a cycle-free,
connected, simple graph.

A final state must be connected, because otherwise there would be two
vertices with no path between them, and then a transition adding the edge
between them would be possible, contradicting finality of the state.

A final state can't have a cycle, because deleting any edge on the
cycle would be a possible transition.}

\eparts

\end{problem}

\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 from the
Notes, which we'll review later in class.)

\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}

\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:  & HP, Bellcore, AT\&T, Draper \\
Carole:     & AT\&T, Bellcore, Draper, HP \\
Eric:   & HP, Draper, AT\&T, Bellcore \\
Radhi:    & Draper, AT\&T, Bellcore, HP
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{c|c}
Company   & Students \\ \hline
AT\&T:    & Radhi, Albert, Eric, Carole \\
Bellcore: & Eric, Carole, Albert, Radhi \\
HP:   & 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:   & HP & 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\\
HP:   & Eric & 2\\
Draper:   & Radhi & 2
\end{tabular}
\end{center}
}
\end{problem}

\begin{problem}
Prove that the Mating Algorithm produces stable marriages.  (Don't look up
the proof in the Course Notes.)

\solution{\begin{proof}
Let Bob be some boy and Carole some girl that he does \emph{not} marry on
the last day of the Mating ritual.  We will prove that Bob and Carole are
not a rogue couple.  Since Bob was an arbitrary boy, it follows that no
boy is part of a rogue couple.  Hence the marriages on the last day are
stable.

To prove the claim, we consider two cases:

\emph{Case} 1.  Carole is not on Bob's list.  Then since invariant $P$
holds, we know that Carole prefers her husband to Bob.  So she's not going
to run off with Bob: the claim holds in this case.

\emph{Case} 2.  Otherwise, Carole is on Bob's list.  But since Bob is not
married to Carole, he must have chosen to serenade his wife instead of
Carole, so he must prefer wife.  So he's not going to run off with Carole:
the claim also holds in this case.
\end{proof}}

\end{problem}

\iffalse

% source: Fall 2000 Problem Set 5
% topics: Matching, intuition

\problempart Give an example of a stable match between 3 boys and 3 girls
where no person gets their first choice.

\solution{Call the boys $1, 2, 3$ and the girls $a, b, c$.  Consider
the following preference list:

\begin{center}
\begin{tabular}{llll||llll} \hline
choice& 1st& 2nd& 3rd& choice& 1st& 2nd& 3rd \\ \hline
1& a& b& c& a& 2& 3& 1 \\
2& b& c& a& b& 3& 1& 2 \\
3& c& a& b& c& 1& 2& 3 \\ \hline
\end{tabular}
\end{center}
   
The matching $(1, b), (2, c), (3, a)$ is stable even though no person
gets their first choice.  

To see the intuition behind this solution, notice first that the first
choice of any boy has that boy as her last choice and vice versa.  
Second, notice that everyone ends up with their second choice.  

Since we show a pairing where everyone has their second choice, this 
is stable because the only way to have a rogue pair is for a boy
or girl to want their first choice, but their first choice always 
likes them least so will never want to leave their current partner.  
Therefore, we end up with a stable pairing where no one gets their
first choice.}

\end{problemparts}
\end{problem}

\begin{problem}
The Stable Buddy Problem is a variant of the Stable Marriage Problem
without the constraint that matched pairs must be Boy with Girl.

In contrast to the Boy-Girl Marriage Problem, there are buddy preferences
where all buddy assignments are unstable.  Give an example of four people
and their preference rankings for which there is no stable way to assign
buddies.  Explain why.

\solution{Let the buddy preferences of four men A, B, C, D be\\
A: BCD\\
B: CAD\\
C: ABD\\
D: $?\: ?\: ?$

Let Y and Z be any two among A, B, and C, and let X be the remaining one.
Notice that the first choices of A, B, C are arranged in a cycle, so that
X must be the first choice of either Y or Z.

Now for any matching into pairs, let Y and Z be the two among A, B, C who
are paired, and X be the one paired with D.  So one of Y and Z, say Y, has X
as his first choice.  But since A, B, C each rank D last, X prefers Y to
his own buddy, D.  So X, Y are a rogue couple.  Notice that the ranking of
A, B, C by D doesn't matter.
}

\end{problem}
\fi

\end{document}
