\documentclass[11pt,macpsfig,psfig,amssymb]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\renewcommand{\solution}[1]{}
%\renewcommand{\solution}[1]{\smallskip \textbf{Solution:} #1}

\newcommand{\bij}{\mathbin{\mbox{\rm bij}}}
\newcommand{\inj}{\mathbin{\mbox{\rm inj}}}
\newcommand{\sur}{\mathbin{\mbox{\rm sur}}}
\newcommand{\ran}[1]{\text{range}(#1)}
\renewcommand{\intersect}{\cap}
\renewcommand{\union}{\cup}
\renewcommand{\Union}{\bigcup}

\renewcommand{\eqdef}{\mathbin{\mbox{::=}}}

\newcommand{\fins}{\mathcal{F}}


\renewcommand{\pts}[1]{\relax[#1 pts]\enskip\ignorespaces}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

%\def\ps@myheadings{%
%    \let\@oddfoot\@empty\let\@evenfoot\@empty
%    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
%    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
%    \let\@mkboth\@gobbletwo
%    \let\sectionmark\@gobble
%    \let\subsectionmark\@gobble
%    }
%
%\makeatother

\begin{document}

%\handout{q1sol}{Quiz 1 Solutions DRAFT 10/6 10:30pm}{October 9, 1999}
\handout{pracq2}{Practice Problems for Quiz 2}{November 2, 1999}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%% Spring 95 %%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
 
Define the poset $(\{1,2,3,4,5\}\times\{1,2,3,4,5\}
,\prec)$ where $(a,b)\prec(c,d)$ 
iff $a\le c$ and $b\le d$.
\bparts
\ppart
Give an antichain which is as long as possible.

\solution{
The antichain is $\{(5,1),(4,2),(3,3),(2,4),(1,5)\}$.
}

\ppart
Prove that the above antichain is the largest.

\solution{
\begin{proof}
  The proof is by contradiction. Say we had a larger antichain.
  Consider the first component of all of the elements of this
  antichain.  They are all integers from $1$ to $5$.  If we had more
  than $5$ elements in the antichain, there must be two elements with
  the same first component (pigeonhole principle).  But then these
  elements are comparable violating the fact we have an antichain.
  Contradiction. Hence we could not have had an antichain with more
  than $5$ elements.

  (An alternate proof would be to show that the poset has a chain
  cover with no more than $5$ elements. Then Dilworth's theorem would
  guarantee us that the largest antichain has at most $5$ elements
  too.)
\end{proof}
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%% Spring 95 %%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
How many permutations of ABCDEFG are there that don't contain
``$\cdots$BEG$\cdots$'' or ``$\cdots$AD$\cdots$''?

\solution{
\begin{tabbing}
Define \= $X = \{ \mbox{permutations of ABCDEFG}\}$\\
\>	$Y  = \{ \mbox{permutations of ABCDEFG that contain BEG}\}$\\
\>	$Z  = \{ \mbox{permutations of ABCDEFG that contain AD}\}$
\end{tabbing}
So, we need to find 
\[
|X|-|Y \cup Z| = |X| - |Y|-|Z| + |Y \cap Z|
\]

$|X|= 7!$ is trivial. $|Y|=5!$ since you can just
consider BEG as one letter: the number of
permutations of \{A, BEG, C, D, F\} is $5!$. 
Similarly, $|Z|=6!$ and $|Y \cap Z|=4!$.\\
\hfill {\bf Answer:} $7!- 5!-6!+4! = 4224$.
}

%%%%%%%%%%%%%%%%%%%%%%%%% Fall 95 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Give tight ($\Theta$) bounds for 
\[{\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}}.\]

\solution{
\begin{eqnarray*}
{\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} \\
{\displaystyle 2x^{\frac{1}{2}}|_1^n} & \leq  {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle 2x^{\frac{1}{2}}|_1^n} \\
2\sqrt{n} - 2 & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 2\sqrt{n} - 1 \\
{\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 2}{\sqrt{n}}} & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 1 + {\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 1}{\sqrt{n}}} \\
2 & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 2 \\
\end{eqnarray*}
That is 
\[ {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} = \Theta(\sqrt{n}).\]
}

%%%%%%%%%%%%%%%%%%%%%%%%% Fall 95 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Rank the following functions by order of growth; that is find an arrangement $g_1 = \alpha(g_2) = \alpha(g_3) = \ldots = \alpha(g_6)$ and state whether $\alpha$ is $O$ or $\Theta$ for each step.
\begin{itemize}
\item $n(\log_2 n)^5$
\item $n^3$
\item $n!$
\item $(n!)^2$
\item $n^n$
\item $3\cdot 8^{\log_2 n} + 4^{\log_2 n}$
\end{itemize}

\solution{
\[ n(\log_2 n)^5 = O(n^3) = \Theta(3\cdot 8^{\log_2 n} + 4^{\log_2 n}) = O(n!) = O(n^n) = O((n!)^2). \]
}

%%%%%%%%%%%%%%%%%%%%%%%%% Fall 96 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
\bparts 
\ppart Suppose that each pair of a genetically engineered species of
rabbits left on an island produces two new pairs of rabbits at the age
of one month and six new pairs of rabbits at the age of two months and
every month afterwards. None of the rabbits ever die or leave the
island.  Find a recurrence relation for the number of {\em pairs} of
rabbits on the island $n$ months after one newborn pair is left on
the island. Do not solve the recurrence relation.

\solution{
Let $N(t)$ be the number of pairs of rabbits after $t$ months. Then
$N(0)=1$, $N(1)=3$, and we have that, for $t \geq 2$:
\begin{displaymath}
N(t) = 7N(t-2) + 3(N(t-1)-N(t-2)) = 3N(t-1) + 4N(t-2)
\end{displaymath}
}
\ppart Solve the following inhomogeneous recurrence relation:
\begin{displaymath} 
f(n) = 6f(n-1)-9f(n-2) +2^n, n \geq 2
\end {displaymath}

The initial conditions are $f(0) = 5, f(1) = 26$.

\solution{
The characteristic equation $r^2-6r+9$ has a repeated root $\alpha =
3$. Hence the homogeneous solution has the form $f_h(n) = A3^n+Bn3^n$,
for some constants $A$ and $B$. To find a particular solution, we try
$f_p(n) = K2^n$. Plugging into the difference equation gives:

\begin{math}
K2^n = 6K2^{n-1} -9K2^{n-2}+2^n \Rightarrow K = \frac{6K}{2} - \frac{9K}{4} +1\\
\Rightarrow 4K= 12K-9K+4 \Rightarrow K = 4
\end{math}
Hence the complete solution has the form $f(n) = A3^n+Bn3^n +2^{n+2}$.
We now use the initial conditions to solve for $A$ and $B$:

\begin{math}
f(0) = 5 = A+4 \Rightarrow A = 1\\
f(10) = 26 = 3 + 3B +8 \Rightarrow B = 5\\
\end{math}
Hence the solution is $f(n) = 3^n + 5n3^n + 2^n, n \geq 2$.
}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%% Fall 97 practicefinal %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem 

\bparts

\ppart 
A vampire arrives in Boston at day $0$ and starts biting people at day
$1$.  People bitten become vampires themselves.  New vampires bite two
persons on the next day after they were bitten and four persons every
day afterwards.  
Write an expression for the number of vampires in $n$ days for $n \geq 2$, 
assuming the first vampire is a newly made vampire.  
{\em Do not solve the recurrence relation.}

\solution{
Let $V(n)$ denote the number of vampires on the $n$th day.
We have the initial conditions $V(0) = 1$ and $V(1) = 3$.

The number of vampires on day $n+1$ is the number of vampires on day $n$
plus all the people that were bitten on day $n$.

$$
V(n+1) = V(n) + 2(V(n)-V(n-1)) + 4V(n-1) = 3V(n) +2V(n-1)
$$
}

\ppart 
Consider the recurrence $T(n)=T(n/2)+T(n/4)+n$ and $T(1)=1$.
Prove that $T(n) \le 4n$, where $n$ is a power of $2$.

\solution{
The base cases are
$T(1) = 1 < 4$, and $T(2) = T(1) +2 = 3 < 8$.

The inductive step is

$$
T(2n) = T(n) + T(n/2) +2n \le 4n + 2n +2n = 8n \leq 4 \cdot 2n.
$$

The induction is complete.
} 

\ppart 
Prove that $T(n)=\Theta(n)$ in the recurrence above.

\solution{
It suffices to show that $T(n) \geq n$.
Indeed, the base cases are $T(1) = 1 \geq 1$, $T(2) = 3 \geq 2$.

$$
T(2n) = T(n) + T(n/2) + n \geq 2n +n/2 \geq 2n.
$$

The induction is complete.

Parts (b) and (c) establish that  $T(n)=\Theta(n)$.
} 
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%% Fall 98 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem One of the three monks working on the famed
Towers of Hanoi project recently rubbed his pained back and burst out,
``Yo!  What are we doing?  This is for chumps!  Let's punt!''  But
before wandering off to start up fast food joints, they must evenly
divide the monastery's collection of prayer beads.

Initially, monk $A$ has 5 beads, monk $B$ has 3 beads, and monk $C$
has 4 beads.  The monastic order has strict rules regarding the
exchange of prayer beads.  Only the following transactions are
allowed.

\begin{enumerate}

\item Monk $B$ may give a bead to monk $A$ at any time.

\item If $C$ has an odd number of beads, then monk $A$ may give a bead to
monk $B$.

\item If $C$ has an even number of beads or monk $A$ has at least two more
beads then monk $B$, then monk $C$ may give or take a bead from either
monk $A$ or monk $B$.
\end{enumerate}

%\begin{problemparts}
\bparts
\ppart  Model the situation with a state machine.
Define the set of states,the set of start states, and the set of
transitions.

\solution{ The set of states $Q$ consists of all triples $(a, b, c)$
such that $a, b, c \geq 0$ and $a + b + c = 12$.  The set of starts
states $Q_0$ consists of the single triple $(5, 3, 4)$.  The set
$\delta$ contains six types of transition:

\[
\begin{array}{rcll}
(a, b, c) & \rightarrow & (a+1, b-1, c) &
	\quad \text{($b > 0$)} \\
\\
(a, b, c) & \rightarrow & (a-1, b+1, c) &
	\quad \text{($a > 0$ and $c$ is odd)} \\
\\
(a, b, c) & \rightarrow & (a-1, b, c+1) &
	\quad \text{($a > 0$ and either $c$ is even or $a \geq b + 2$)} \\
(a, b, c) & \rightarrow & (a, b-1, c+1) &
	\quad \text{($b > 0$ and either $c$ is even or $a \geq b + 2$)} \\
(a, b, c) & \rightarrow & (a+1, b, c-1) &
	\quad \text{($c > 0$ and either $c$ is even or $a \geq b + 2$)} \\
(a, b, c) & \rightarrow & (a, b+1, c-1) &
	\quad \text{($c > 0$ and either $c$ is even or $a \geq b + 2$)}
\end{array}
\]
}

\ppart Prove that the monks can reach the state
where monk $A$ has 0 beads, monk $B$ has 9 beads, and monk $C$ has 3
beads by describing a sequence of steps leading to this state.

\solution{
Initially, monk $C$ gives a bead to monk $B$ using rule 3.  Then monk
$A$ gives his 5 beads to monk $B$ using rule 2 repeatedly. }


\ppart  Prove that the monks can not reach the state
where every monk has 4 beads by using the Invariant Theorem.

\solution{
\begin{proof}
The proof uses the Invariant Theorem.  We prove that if monk $C$ has
an even number of beads, then monk $A$ has more beads than monk $B$.
This implies that the monks can never evenly divide up the prayer
beads; an even division would require that $C$ have 4 beads, but then
the invariant would imply that $A$ has more beads then $B$.

The invariant holds in the single start state $Q_0$, since in this
case monk $C$ has an even number of beads (4), and monk $A$ has more
beads than monk $B$ (5 vs. 3).  Furthermore, if the invariant holds
before a transition, then it holds after a transition.  There are six
cases to check, corresponding to the six types of transition.

\begin{enumerate}
\item $(a, b, c) \rightarrow (a+1, b-1, c)$ where $b > 0$.  If $c$ is
odd, then the invariant holds after the transition because the
hypothesis of the invariant if false.  If $c$ is even, then the
invariant holds after the transition because $a + 1 > a > b > b - 1$.

\item $(a, b, c) \rightarrow (a-1, b+1, c)$ where $a > 0$ and $c$ is
odd.  The invariant holds after the transition because the hypothesis
of the invariant is false.

\item $(a, b, c) \rightarrow (a-1, b, c+1)$ where $a > 0$ and either
$c$ is even or $a \geq b + 2$.  If $c$ is even, then the invariant
holds after the transition because the hypothesis is false.  If $c$ is
odd, then the invariant holds after the transition because the
conclusion is true; that is, monk A has more beads than monk B.
\end{enumerate}

The argument in the remaining three cases is identical to the argument
for case 3.  Since the invariant hold in all start states and is
maintained under all transitions, the claim is proved by the Invariant
Theorem.
\end{proof}
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%% Spring 99 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\problem We apply the following procedure to a digraph $G=(V,E)$:
pick two vertices $v_1 \neq v_2$ such that (1) there is an edge in $E$
from $v_1$ to $v_2$ and (2) there is also a path from $v_1$ to $v_2$ which
does \emph{not} include this edge, and then delete the edge $(v_1,v_2)$.
Keep repeating this deletion process until it is no longer possible to
delete any edge.

This procedure can be modelled as a state machine whose states are all the
subgraphs of $G$, that is, all the digraphs with vertices $V' \subseteq V$
and edges $E' \subseteq E$.  $G$ is the only start state, and the final
states are the subgraphs in which no deletions are possible.

\bparts
\ppart Let $G$ be the digraph with $V=\set{1,2,3,4}$ and edges
\[
\set{(1,2),(2,1),(2,3),(3,2),(3,1),(2,4)}.
\]
List the possible final states that are reachable from the start state: 

\solution{2 states --- a cycle 1231 or a double loop 21232,
with 2 connected to 4 in each case:
\[
\set{(1,2),(2,3),(3,1),(2,4)},
\]
and
\[
\set{(1,2),(2,1),(2,3),(3,2),(2,4)}.
\]}

\ppart In addition to numerical derived variables, we introduce
some set-valued derived variables below.  For the set-valued derived
variables, values will be partially ordered under containment (that is,
under $\subseteq$).  So such a variable is \emph{decreasing} when its value
after a transition is strictly contained in its value before the
transition.  This also applies to relation-valued variables, since a
relation can be treated as the set of tuples of its related elements.

On the line next to each of the variables below, indicate the strongest
property which it satisfies from the following list:
\begin{center}
\begin{tabular}{ccccc}
invariant & increasing & decreasing & nonincreasing & nondecreasing
\end{tabular}
\end{center}
The derived variables are:
\begin{enumerate}

\item[i)] the set of vertices, \brule{1.5in}

\solution{invariant}

\item[ii)] the set of edges, \brule{1.5in}

\solution{decreasing}

\iffalse
\item minimum number transitions to reach a final state, \brule{1in}

\solution{nonincreasng? fluctuates?}
\fi

\item[iii)] the connectedness relation, $\succeq$, \brule{1.5in}\\
(remember for vertices $u,v$:\
$u \succeq v$ iff $u=v$ or there is a path from $u$ to $v$),

\solution{invariant}

\item[iv)] the set of final states reachable from the current state,

\solution{nonincreasing}
\iffalse

\item[v)] the number of simple cycles. \brule{1.5in}
\fi

\item[v)] the minimum length of a path in the graph. \brule{1.5in}

\solution{invariant; it's always 1 --- or undefined if the graph has no edges.}

\end{enumerate}

\ppart Prove that the procedure terminates and that the final
digraph has the same connectedness relation as $G$.

\solution{Since the edge set is decreasing so is the number of edges.  Since
it must be a natural number, by the Well-ordering Principle it cannot
decrease forever, and the procedure terminates when it can no longer be
decreased.  The final graph has the same connectedness relation as $G$
because the relation is an invariant.}

\ppart Does it also follow from the indicated properties of the
derived variables that the final graph has the minimum number of
edges among all graphs with the same connectedness relation as $G$?
Briefly explain.

\solution{Having the minimum number of edges
does not follow because it isn't true, eg, the graph with edges
$\set{(1,2),(2,1)(2,3),(3,2)}$ is a final state with four edges;
$\set{(1,2),(2,3),(3,1)}$ has the same connectedness with only three edges.

Another example is the one vertex graph with a self-loop; anyone picky
enough to spot this degenerate case deserves full credit.}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%% fall 98 ps3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
A {\em linear extension} of a poset is a
total order consistent with the partial order.  That is, if $x > y$ in
the partial order, then $x > y$ in the total order also.  For example,
in the poset defined by the Hasse diagram below, the following
relationships hold: $a > b$, $a > c$, $a > d$, $a > e$, $b > c$, and
$b > d$.

\begin{figure}[h]
\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-partial.eps}}}
\end{figure}

This poset has eight linear extensions, which are listed in the table below.  To
clarify the notation, the upper-left entry represents the total order
where $a$ is the largest element, $b$ the second largest, and so
forth.  Note that all of the relationships that hold in the poset also
hold for all the total orders listed below.

\[
\begin{array}{ccc}
a > b > c > d > e	& \quad \quad &		a > b > d > c > e \\
a > b > c > e > d	&	&		a > b > d > e > c \\
a > b > e > c > d	&	&		a > b > e > d > c \\
a > e > b > c > d	&	&		a > e > b > d > c
\end{array}
\]

\bparts

\ppart List all the linear extensions of the poset represented by the
Hasse diagram below.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-partial2.eps}}}
\end{figure}

\solution{
\[
\begin{array}{ccc}
a > b > c > e > d	& \quad \quad &		a > c > b > e > d \\
a > b > c > d > e	&	&		a > c > b > d > e \\
a > b > d > c > e
\end{array}
\]
}

\ppart  

{\bf Claim.} The number of linear extensions of a partially ordered
set with $n$ elements always divides $n!$.

Either prove that his claim is correct for all posets or else draw
the Hasse diagram of a counterexample and list all linear extensions.

\solution{
The claim is false.  The 4-element poset depicted below has 5 linear
extensions.  This is a counterexample, because 5 does not divide 4!.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-poset-cx.eps}}}
\end{figure}

\[
\begin{array}{ccc}
a > b > c > d	& \quad \quad &		a > b > d > c \\
b > a > c > d   &	&		b > a > d > c \\
b > d > a > c
\end{array}
\]
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% fall 98 ps3 %%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem 
A relation $R$ on a set $A$ is {\em weakly
transitive} if for all $a, b, c, d \in A$, the relations $aRb$, $bRc$,
and $cRd$ imply the relation $aRd$.

Prove or disprove the following statements.

\bparts

\ppart Every symmetric, weakly transitive relation is transitive.

\solution{
The claim is false.  The diagram below shows a counterexample.

\begin{figure}[h!]
\centerline{\resizebox{!}{1.0in}{\includegraphics{ps3-relation-cx.eps}}}
\end{figure}
}

\ppart Every reflexive, symmetric, weakly transitive relation
is an equivalence relation.

\solution{
\begin{proof}
The relation $R$ is an equivalence relation if it is reflexive,
symmetric, and transitive.  The first two properties hold by
assumption; all that remains is to show that $R$ is a transitive
relation.  Suppose that the relations $aRb$ and $bRc$ hold.  Because
$R$ is reflexive, the relation $aRa$ also holds.  Because $R$ is
weakly transtive, the relations $aRa$, $aRb$, and $bRc$ imply the
relation $aRc$.  Therefore, $R$ is transitive.
\end{proof}
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%% fall 97 ps3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem

We provide an alternative definition for a tree.

{\em Definition:} A {\em tree} is a connected graph such that
$\forall u,v \in V$, there is a unique path connecting $u$ to $v$.

Prove that this definition is equivalent to the one that defines a tree
to be an acyclic graph of $n$ vertices that has $n-1$ edges.

\solution{
Let $G$ be a graph  of $n$ vertices such that
$\forall u,v \in V$, there is a unique path connecting $u$ to $v$.

First we show that $G$ is acyclic.
Suppose, for the purposes of contradiction, that $G$ has a cycle.
Pick two vertices $u$ and $v$ on the cycle.  Then there are at least
two paths connecting $v$ and $u$, contradicting the uniqueness assumption.
So $G$ is acyclic.

Also we note that the existence of paths between every two vertices
 implies that
$G$ is connected.  So $G$ is a connected acyclic graph, and from class
we know that it has $n-1$ edges.

Conversely, let $G$ be an acyclic graph with $n$ vertices and $n-1$ edges.
We know from class that such a graph is connected so there exists at least 
one path between any two vertices.

Suppose, for the purposes of contradiction, that there are two distinct
paths $C$ and $C'$ connecting the vertices $u$ and $v$. 
Starting at $u$ consider the first vertex $u'$ where $C$ differs 
from $C'$ (such a vertex exists because the graphs are distinct).  
Also consider the first vertex $v'$ where $C$ and $C'$ meet again
(such a vertex exists because both paths end at $v$).  Then there is a
simple cycle that starts at $u'$ follows $C$ until it reaches $v'$ and
returns to $u'$ following $C'$.
This contradicts the acyclicity of the graph.
}

%%%%%%%%%%%%%%%%%%%%%%%% fall 97 ps3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem

Let $G$ be a simple graph.  Define a relation $R$ on the set of vertices $V$
of $G$ by $(v,u) \in R$, if there is a path connecting $u$ to $v$.

\bparts

\ppart 
Verify that $R$ is an equivalence relation.

\bigskip
\solution{
\begin{itemize}

\item Reflexivity:

$R$ is reflexive because trivially every vertex is connected to itself.

\item Symmetry:

Suppose there is a path $(u,x_1), (x_1,x_2), \ldots, (x_n,v)$ connecting 
$u$ to $v$.
Then, the path $(v,x_n), \ldots, (x_1,u)$ connects $v$ to $u$. 
Therefore, $R$ is symmetric.

\item Transitivity:

Let the path $(u,x_1), (x_1,x_2), \ldots, (x_n,v)$ connect $u$ to $v$, and
the path \\
$(v,y_1), (y_1,y_2), \ldots, (y_m,w)$ connect $v$ to $w$.

Then the path $(u,x_1), \ldots, (x_n,v), (v,y_1), \ldots ,(y_m,w)$
connects $u$ to $v$.\\
Therefore $R$ is transitive.

\end{itemize}
}
\ppart What are the equivalence classes of $R$?

\bigskip
\solution{
The equivalence classes of $R$ are the connected components of $G$.
}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% fall 97 ps4 %%%%%%%%%%%%%%%%%%%%

\problem 
In this problem we consider a protocol for college admissions.
There are $N$ students $S_1,...,S_N$ and $M$ universities $U_1,...,U_M$.  
Each student provides a preference ranking of all $M$ universities and each 
university provides a preference ranking of all $N$ students.  
For each $i$ university $U_i$ has $n_i$ slots to fill
and sum of all slots is equal to the number of students. 
That is, $\sum_{i=1}^M n_i = N$.

Consider the following protocol for assigning students to universities.

\begin{enumerate}
\item Each student applies to their favorite university that he/she has not yet
ruled out.

\item University $i$ says 
``maybe'' to the $n_i$ applicants with the better ranking.
(They say ``maybe'' to everyone if they have less that $n_i$ applicants).
They say ``no way'' to the rest.

\item Any students who is turned down crosses the university of his/her list.
\end{enumerate}

\bparts
\ppart
Model the problem as a state machine.  State clearly what the states and
state transitions are. What is the start state? 

\solution{
The state is given by a vector of $N$ arrays containing the crossed out 
universities for each student.  The preference list for each student can be
included as part of the state or can be considered as universal constants.
The state transitions are described by the universities that are crossed off
in any time steps. There is only one initial state with no names crossed off
any list.

{\bf Termination condition:} When no university has more than $n_i$ applicants,
each university accepts the remaining applicants.
}

\ppart
Use derived variables to prove termination.
How long does the protocol take to terminate?

\solution{
\begin{theorem}
The algorithm terminates in at most $NM$ steps.
\end{theorem}

\begin{proof}
Define the derived variable $f:Q \rightarrow \nat$ given by

$f(q)=$ number of universities over all students' lists that are not 
crossed off.

$f$ is decreasing because at every step before termination at least 
one name is crossed of the lists.
Note that Initially no university is crossed off,
so there are a total $NM$ universities in the lists.

\begin{center}
execution time $\leq f(q_0) \leq NM$.
\end{center}

\end{proof}
}
\eparts

\end{problems}

\end{document}