
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Midterm
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (12 points)} 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}
\problempart {\bf (3 points)}  Model the situation with a state machine.
Define the set of states,the set of start states, and the set of
transitions.

\examonly{\vspace{2.5in}}

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

\problempart {\bf (3 points)}  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. }

\examonly{\newpage}

\problempart {\bf (6 points)}  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}
}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points)} Consider the following procedure for
computing the greatest common divisor ($\gcd$) of a non-empty list of
positive integers $(x_1, x_2, \ldots, x_n)$.

If all entries in the list are equal, then the procedure outputs the
common value and terminates.  Otherwise, the procedure selects two
entries with different values and replaces the larger one by the
difference.

We can model this procedure with a state machine as follows.

\begin{itemize}

\item The set of states $Q$ consists of all lists of $n$ positive
integers.

\item The set of start states $Q_0$ consists of the single state $(x_1,
x_2, \ldots, x_n)$.

\item The set $\delta$ contains all transitions of the form

\begin{eqnarray*}
(y_1, y_2, \ldots, y_i, \ldots, y_j, \ldots, y_n)
    & \rightarrow &
(y_1, y_2, \ldots, y_i - y_j, \ldots, y_j, \ldots, y_n)
\end{eqnarray*}

where $i$ and $j$ are distinct numbers in the range $1$ to $n$ and
$y_i > y_j$.  (Note that the transition is written with $y_i$
preceding $y_j$, but that the reverse order is also possible.)

\end{itemize}

\begin{problemparts}

\problempart {\bf (5 points)} Prove that the procedure terminates.

\solution{We construct a non-negative, decreasing derived variable.
This implies that the machine reaches at state with no outgoing
transitions.  All such states are terminating states of the procedure.

Define the derived variable $S$ to take on the value $y_1 + y_2 +
\ldots + y_n$ in the state corresponding to the list $(y_1, y_2,
\ldots, y_n)$.  This derived variable is non-negative, since all $y_i$
are positive.  The derived variable is decreased by each transition,
since the list entry $y_i$ is decrease by $y_j$ (a positive quantity)
and all other list entries are unchanged.}
\problempart {\bf (10 points)} Prove that the procedure computes the
$\gcd$ of $x_1, x_2, \ldots, x_n$.  State explicitly any number theoretic
facts that you use, but do not prove them.

\solution{The proof uses the Invariant Theorem.  We will prove the
invariant that in state $(y_1, y_2, \ldots, y_n)$,

\begin{eqnarray*}
\gcd(y_1, y_2, \ldots, y_n) & = & \gcd(x_1, x_2, \ldots, x_n).
\end{eqnarray*}

The invariant hold trivially in the start state.  Futhermore, the
invariant holds after a transition if it holds prior to a transition:

\begin{eqnarray*}
\gcd(y_1, y_2, \ldots, y_i - y_j, \ldots, y_j, \ldots, y_n)
    & = &   \gcd(y_1, y_2, \ldots, y_i, \ldots, y_j, \ldots, y_n) \\
    & = &   \gcd(x_1, x_2, \ldots, x_n)
\end{eqnarray*}

The first step is justified by the following number-theoretic fact.
For positive integers $z_1, z_2, \ldots, z_n$,

\begin{eqnarray*}
\gcd(z_1, z_2, \ldots, z_i, \ldots, z_j, \ldots, z_n)
    & = &   \gcd(z_1, z_2, \ldots, z_i - z_j, \ldots, z_j, \ldots, z_n)
\end{eqnarray*}

provided $z_i > z_j$.  The second step in the argument above is
justified by the assumption that the invariant holds prior to the
transition.  Therefore, the invariant holds by the Invariant Theorem.

This invariant implies that the output of the procedure is correct.
If $(y_1, y_2, \ldots, y_n)$ is a terminating state, then

\begin{eqnarray*}
y_1 = y_2 = \ldots = y_n
    & = &   \gcd(y_1, y_2, \ldots, y_n) \\
    & = &   \gcd(x_1, x_2, \ldots, n_n).
\end{eqnarray*}

The second step uses the invariant.
}
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{16} \textbf {Counting Connected Components of a Graph}

Consider the following algorithm, which counts the number of connected
components in a graph by ``contracting'' edges until there are no edges
left in the graph.

\begin{tabbing}
XXXX\=XXXX\=\kill
{\bf CompCount} (Undirected Graph $G$)\\
1.  $H := G$\\
2.  While $H$ contains at least one edge do:\\
\>1.  Pick an edge $(v, w)$ in $H$.\\
\>2.  Add a new vertex $z$ to $H$.\\
\>3.  For each vertex $p$ in the graph, add the edge $(p,z)$ to $H$\\
\>\>if and only if $(p,v)$ or $(p,w)$ is an edge in $H$.\\
\>4.  Remove vertices $v, w$ and all their incident edges from $H$.\\
3.  $n := $ the number of vertices in $H$.\\
4.  CompCount $(G) := n$
\end{tabbing}

\problempart {\bf (3 points)} If $H$ is the graph given below, and the
edge $(v,w)$ is the one selected in step 2.1, draw the graph $H$ after
step 2.4 in the algorithm.  Label the $z$ vertex in your graph.

\includegraphics[height=3in]{problem2a.eps}

\solution{\bigskip {\bf Solution:}
\includegraphics[height=3in]{problem2asol.eps}
}

\problempart {\bf (3 points)} Model this algorithm as a state machine.

\solution{\bigskip {\bf Solution:}

The states of the machine will be pairs $(G, H)$ where $G$ and $H$ are
graphs.  

The start state $q_0$ of the machine will be pairs $(G, G)$ where $G$
is some graph.

The transitions are of the form $(G, H) \mapsto (G, H'_{(v,w)})$.
They exist as long as $H$ has any edges, and for each edge $(v,w)$ in
$H$ there is a transition.

The graph $H'$ has all the same vertices as $H$, except that $v$ and
$w$ are replaced by a single vertex $z$.  The edges between vertices
not involving $v$ and $w$ are in $H'$, and for any other vertex $x$,
there is an edge between $x$ and $z$ in $H'$ if and only if there is
an edge between $x$ and $v$ or between $x$ and $w$ in $H$.
}
\problempart {\bf (7 points)} Prove, using an invariant, that if the
algorithm terminates, the output is the number of connected components
of $G$.  You may assume that in a graph with no edges, the number of
connected components is equal to the number of vertices.

\solution{\bigskip {\bf Solution:}

Let our invariant $P(q)$ be, ``In state $q$, $H$ has the same number
of connected components as $G$.''

The invariant is clearly true in the start state, since $H$ and $G$ are
the same graph.

Suppose that $(G, H'_{(v,w)})$ is a state reachable from $(G, H)$.  
Since there is an edge from $v$ to $w$ they must be in a connected component.
Clearly, all other connected components still exist in $H'$ so there is no
problem.  We must prove that those vertices corresponding to the connected 
component including $v$ and $w$ form a connected component in $H'$.

Suppose $x$ is in the same connected component as $v$ and $w$ but $x$
is different from both $v$ and $w$.  Then there is a path from $x$ to
$v$ in $H$, so there is a path from $x$ to $z$ in $H'$.  (To make it,
simply reuse any edge not involving $v$ or $w$, or use the edge from
$y$ to $z$ instead of the edge from $y$ to $v$ or $y$ to $w$, and drop
the edge $(v,w)$ if it appears.)  

So, if $x$ is a vertex in the connected component with $v$ and $w$ in
$H$, then any vertex coming from $x$ (either $x$ itself if $x \neq v$
and $x \neq w$ or $z$ otherwise) is in the same connected component as $z$.

Furthermore, if $x$ is a vertex in another connected component from
$v$ and $w$ in $H$, then there is no path from $x$ to $z$.  If there
were, there must have been a path from $x$ to either $v$ or $w$ but
there was not.

Thus, the invariant is proven.  If the algorithm reaches a point where
there are no edges, the number of connected components is the number
of points.  Thus, if the algorithm terminates, it outputs the number
of connected components of $G$.
}

\largespace

\problempart {\bf (3 points)} Prove that this algorithm always terminates.

\solution{\bigskip {\bf Solution:}

Let $F(G, H)$ be the number of edges in $H$.  $F$ is clearly always a
nonnegative integer since graphs cannot have non-integer or negative
numbers of edges.  Furthermore, $F$ is strictly decreasing.  

When we make the transition from $H$ to $H'$ we remove the edge $(v,
w)$, and we may remove other edges too (if there are edges from some
node $x$ to both $v$ and $w$, these will be replaced with only one
edge from $x$ to $z$ in $H'$.)  

By the termination theorem, this algorithm terminates.
}








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Quiz 1
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
problem\pts{20}  Bags and Stacks

This problem involves two labeled state machines,
called $\ms{Bag}$ and $\ms{Stack}$, each of which keeps track of a
collection of integers. 
A ``client'' can interact with each using requests and responses.
Both support the same kinds of operations: $\ms{insert}$ and
$\ms{get}$, though the operations behave a little differently in the
two machines.

$\ms{Bag}$ maintains a ``bag'' of integers, which is like a set of
integers except it allows repeats. 
Written out in detail: 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\= \kill
$\ms{Bag}$ Labeled State Machine: \\
\\
$Q$: 
\> $B$, a bag of integers \\
\> $\ms{req}$, either $\ms{insert}(x)$, $\ms{get}$, or $\ms{null}$ \\
\> $\ms{resp}$, either $\ms{OK}$, an integer, $\ms{error}$, or
$\ms{null}$ \\
\\
$Q_0$: 
\> $B$ is the empty bag, $\ms{req} = \ms{resp} = \ms{null}$ \\
\\
$L$:
\> Input: $\ms{insert}(x)$, $\ms{get}$ \\
\> Internal: $\ms{perform}(\ms{insert}(x))$,$\ms{perform}(\ms{get})$ \\
\> Output: $\ms{respond}(r)$\\
\\
$\delta$:
\> $\ms{insert}(x)$:\\ 
\> \> Can occur:  Anytime \\ 
\> \> Effect: if $\ms{req} = \ms{null}$ then $\ms{req} := \ms{insert}(x)$ \\
\> $\ms{get}$: \\
\> \> Can occur:  Anytime \\
\> \> Effect: if $\ms{req} = \ms{null}$ then $\ms{req} := \ms{get}$ \\
\> $\ms{perform}(\ms{insert})$: \\
\> \> Can occur if: $\ms{req} = \ms{insert}(x)$ \\
\> \> Effect: add $x$ to $B$; $\ms{resp} := $\ms{OK} \\
\> $\ms{perform}(\ms{get})$: \\
\> \> Can occur if: $\ms{req} = \ms{get}$ \\
\> \> Effect: \\
\> \> \> if $B$ is nonempty then \\
\> \> \> \> choose any element $x$ in $B$ and remove one copy from $B$; \\
\> \> \> \> $\ms{resp} := x$ \\
\> \> \> else $\ms{resp} := \ms{error}$ \\ 
\> $\ms{respond}(r)$: \\
\> \> Can occur if: $\ms{resp} = r$, $r \not= \ms{null}$ \\
\> \> Effect: $\ms{req} := \ms{null}$; $\ms{resp} := \ms{null}$
\end{tabbing}

\nextproblem
The other machine, $\ms{Stack}$, differs from $\ms{Bag}$ only in its
state and the $\ms{perform}$ transitions:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\= \kill
$\ms{Stack}$ Labeled State Machine: \\
\\
$Q$: 
\> $S$, a sequence of integers \\
\> $\ms{req}$, $\ms{resp}$, as for $\ms{Bag}$ \\
\\
$Q_0$:
\> $S$ is the empty sequence, $\ms{req} = \ms{resp} = \ms{null}$ \\
\\
$\delta$:\> $\ms{perform}(\ms{insert})$: \\
\> \> Can occur if: $\ms{req} = \ms{insert}(x)$ \\
\> \> Effect: $S = x S$, where $x S$ is the concatenation of $x$ and $S$; \\
\> \> \>  $\ms{resp} := $\ms{OK} \\
\> $\ms{perform}(\ms{get})$: \\
\> \> Can occur if: $\ms{req} = \ms{get}$ \\
\> \> Effect: \\
\> \> \> if $S$ is nonempty then \\
\> \> \> \> $\ms{resp} := \ms{head}(S)$ (the first element of $S$); \\
\> \> \> \> $S := \ms{tail}(S)$ (all but the first element)\\
\> \> \> else $\ms{resp} := \ms{error}$ 

\end{tabbing}

For this problem, you need give only a trace or an abstraction relation
that works to justify your answer.  If you give an abstraction relation,
you do not have to prove it is correct.

\problempart{\bf (10 points)}
Does $\ms{Stack}$ implement $\ms{Bag}$?
If your answer is yes, then give an abstraction
relation.  If it is no, then give an example of a
trace of $\ms{Stack}$ that is not a trace of $\ms{Bag}$.  


\solution{\bigskip 

{\bf Solution:} Yes.  An abstraction relation from {\em Stack} to {\em Bag}
is as follows:

$$(S, req, resp) \to (B_S, req, resp)$$

where the multiset $B_S$ is defined as follows: $B_S = \{x | x$
appears in $S\}$.  That is $x$ appears in $B_S$ exactly as many times
as it appears in the sequence $S$.  All transition labels are given
the same names.  }
\smallspace


\problempart{\bf (10 points)} Does $\ms{Bag}$ implement $\ms{Stack}$?
If so, give an abstraction relation.  If not, give a 
trace of $\ms{Bag}$ that is not a trace of $\ms{Stack}$.

\solution{\bigskip

{\bf Solution:} No.  Let $x$ and $y$ be different.

The trace {\em insert(x), respond(OK), insert(y), respond(OK), get, respond(x)}
is a trace of {\em Bag} but it is not a trace of {\em Stack}.  In stack, the
only available transition after the {\em get} would be a {\em respond(y)}.  
Since $x \neq y$, the two are different.  }






