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

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

\begin{document} 
\inclassproblems{7, Wed.}

%% F03 rec4
%% source: Fall99 Q2, prob 4, Final exam Fall02
%% topics: {Graphs, Trees, State Machines, Counting, Well-order}

\begin{problem}

Given a simple graph $G$, we apply the following operation to the
graph: 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 or, there is no path from $u$ to $v$; in which case, add the edge
$\set{u,v}$.
\end{enumerate}

We 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$.  The start state
is $G$, 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} For any state, $G'$, let $e$ be the number of
edges in $G'$, $c$ be the number of connected components it has, and $s$
be the number of simple cycles.  For each of the derived variables below,
indicate the \emph{strongest} of the properties that it is guaranteed to
satisfy, no matter what the starting graph $G$ is.  The choices for
properties are: \emph{constant}, \emph{strictly increasing},
\emph{strictly decreasing}, \emph{weakly increasing}, \emph{weakly
decreasing}, \emph{none of these}.  The derived variables are
 
\begin{enumerate}
%%\item[(i)] $e$ \hfill\brule{2in}\solution{none of these}
%%\item[(ii)] $c$ \hfill\brule{2in} \solution{weakly decreasing}
%%\item[(iii)] $s$ \hfill\brule{2in} \solution{weakly decreasing}

\item[(i)] $e-s$  \solution{weakly increasing}

\item[(ii)] $c+e$  \solution{weakly decreasing}

\item[(iii)] $3c + 2e$  \solution{strictly decreasing}

\item[(iv)] $c+s$ \solution{strictly decreasing}

\item[(v)] $(c,e)$, partially ordered coordinatewise (the \emph{product}
partial order). \solution{weakly decreasing}

\iffalse
\item[(v)] $(c,e)$, ordered lexicographically \hfill\brule{2in}
\solution{strictly decreasing}
\fi

\end{enumerate}


\ppart Choose a derived variable from above and prove that it is
strictly decreasing in some well-founded partial order.  Conclude that the
procedure terminates.

\solution{
To show that the variable (ii) strictly 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 $c$. Meanwhile the 
number of edges $e$ decreases by one when an edge is deleted. Therefore
the variable $3c+2e$ decreases by $2$. The rule for adding an edge ensures 
that the number of connected components $c$ decreases by one and the number
of edges $e$ increases by one. Therefore the variable $3c+2e$ decreases by
$1$.

To show that the variable (iii) strictly decreases, note that the rule for
deleting an edge ensures that the number of connected components $c$ 
does not change and the number of simple cycles $s$ decreases by $n$, 
where $n \geq 1$. Therefore the variable $c+s$ decreases by $n$. The rule for 
adding an edge ensures that the number of connected components $c$ decreases
by one and the number of simple cycles $s$ does not change. Therefore the 
variable $c+s$ decreases by one.

To show that the lexicographically ordered $(c,e)$ strictly decreases, 
note that the rule for deleting an edge ensures that the number of connected components
$c$ does not change and the number of edges $e$ decreases by one.
The rule for adding an edge ensures that the number of connected components $c$
decreases by one.}

\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*}
See if you can come up with a stable marriage assignment given the
following preferences.  You are not expected to know/remember the Dating
Protocol that solves this problem and which is about to be covered in
lecture.  (And if you do remember the protocol, don't spoil your
teammates' fun by telling them.)

\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*}
\end{problem*}

\solution{See Slides 7-2
(\href{http://theory.csail.mit.edu/classes/6.042/spring04/handouts/slides7-2.pdf}{pdf}).}

%%F03 rec4

\instatements{\newpage}
\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 \\
Karen:     & AT\&T, Bellcore, Draper, HP \\
Eric:   & HP, Draper, AT\&T, Bellcore \\
Kilian:    & Draper, AT\&T, Bellcore, HP
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{c|c}
Company   & Students \\ \hline
AT\&T:    & Kilian, Albert, Eric, Karen \\
Bellcore: & Eric, Karen, Albert, Kilian \\
HP:   & Kilian, Eric, Albert, Karen \\
Draper:   & Karen, Kilian, Eric, Albert
\end{tabular}
\end{center}
\bparts

\ppart
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\\
Karen:     & AT\&T & 1\\
Eric:   & HP & 1\\
Kilian:    & 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: & Karen & 2\\
HP:   & Eric & 2\\
Draper:   & Kilian & 2
\end{tabular}
\end{center}
}

\iffalse

\ppart Describe a simple procedure to determine whether any given
stable marriage problem has a unique solution, \ie only one possible
stable marriage assignment.

\solution{
See if the Mating algorithm with Boys as suitors yields the same solution
as the algorithm with Girls as suitors.  These two marriage assignments
are boy-optimal and girl-optimal, respectively, so they agree iff there is
a unique solution.
}

\fi

\eparts

\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}
We have that the following predicate, $P$, is an invariant of the Mating
ritual:
\begin{quote}
For every girl, $G$, and every boy, $B$, if $G$ is crossed off $B$'s list,
then $G$ has a favorite suitor and she prefers him over $B$.
\end{quote}

Now let Bob be some boy and Carole be any girl that he is \emph{not}
married to 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 his wife.  So he's not going to run off with
Carole: the claim also holds in this case.
\end{proof}}

\end{problem}

\end{document}
