\documentclass[12pt,oneside]{article}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphics}
\input{macros-course}

\showsolutionstrue


\begin{document}

\handout{pquiz1-sol}{Practice Quiz 1 - Solutions}{March 11, 2001}
%\pquiz{1}{March 8, 2001}

\newcommand{\us}[1]{\underline{#1}}
\newcommand{\examonly}[1]{}
\newcommand{\unspace}{\vspace{-0.75ex}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problems}

\problem  {\bf (6 points)} Consider the following proposition.
\[
\forall x \forall y \ (x < y \rightarrow \exists z \ (x < z \wedge z < y))
\]

\begin{problemparts}

\problempart {\bf (2 points)}  Prove or disprove this proposition,
assuming that the universe is the set of integers.


\solution{ The proposition is false.  In the case where $x = 0$ and $y
= 1$, there does not exist an integer $z$ such that $x < z$ and $z <
y$.  }

\problempart {\bf (4 points)}  Write the negation of this proposition.
Your solution may {\em not} use the $\neg$ symbol, but may use any of
the relations $=$, $<$, $>$, $\leq$, or $\geq$.


\solution{
\[
\exists x \exists y \ (x < y \wedge \forall z \ (x \geq z \vee z \geq y))
\]
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\problem {\bf (10 points)} Define the matrix

\begin{eqnarray*}
M & = & \left[
\begin{array}{cc}
0 & 1 \\
1 & 1
\end{array}
\right].
\end{eqnarray*}
Let $M^n$ denote the product of $n$ copies of the matrix $M$.  Use
ordinary induction to prove that for all $n \geq 1$, the upper right
entry of $M^n$ is $F_n$, the $n$-th Fibonacci number.  State your
inductive hypothesis clearly.

For reference, the standard formula for the product of $2 \times 2$
matrices is given below.
\begin{eqnarray*}
\left[
\begin{array}{cc}
a & b \\
c & d
\end{array}
\right]
\cdot
\left[
\begin{array}{cc}
e & f \\
g & h
\end{array}
\right]
& = &
\left[
\begin{array}{cc}
ae + bg & af + bh \\
ce + dg & cf + dh
\end{array}
\right]
\end{eqnarray*}
Recall that $F_0 = 0$, $F_1 = 1$, $F_2 = 1$, $F_3 = 2$, \ldots.

\solution{
\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that

\begin{eqnarray*}
M^n & = & \left[
\begin{array}{cc}
F_{n-1} & F_n \\
F_n & F_{n+1}
\end{array}
\right].
\end{eqnarray*}
In the base case, $P(1)$ is true because
\begin{eqnarray*}
M^1 & = & 
\left[
\begin{array}{cc}
0 & 1 \\
1 & 1
\end{array}
\right] \\
& = &
\left[
\begin{array}{cc}
F_0 & F_1 \\
F_1 & F_2
\end{array}
\right].
\end{eqnarray*}
\end{proof}
In the inductive step, for $n \geq 1$ assume $P(n)$ to prove $P(n+1)$.
The following equalities hold.
\begin{eqnarray*}
M^{n+1} & = &   M^n \cdot M \\
        & = &   \left[
                \begin{array}{cc}
                F_{n-1} & F_n \\
                F_n & F_{n+1}
                \end{array}
                \right] \cdot
                \left[
                \begin{array}{cc}
                0 & 1 \\
                1 & 1
                \end{array}
                \right] \\
        & = &   \left[
                \begin{array}{cc}
                F_n & F_{n-1} + F_n \\
                F_{n+1} & F_n + F_{n+1}
                \end{array}
                \right] \\
        & = &   \left[
                \begin{array}{cc}
                F_n & F_{n+1} \\
                F_{n+1} & F_{n+2}
                \end{array}
                \right]
\end{eqnarray*}

The first step uses the definition of $M^n$.  The second step uses the
induction hypothesis and the definition of the matrix $M$.  We carry
out a matrix multiplication in the third step and use the Fibonacci
recurrence in the last step.  This shows that $P(n)$ implies $P(n+1)$,
and the claim is proved by induction.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\examonly{\newpage}

\problem {\bf (12 points)} The vertices of a directed graph can be
partitioned into {\em strongly-connected components}.  Two vertices
$u$ and $v$ belong to the same strongly connected component if there
is a path from $u$ to $v$ and a path from $v$ to $u$.  A strongly
connected component may consist of a single vertex.

Math Moose has noticed a strange phenomenon.  He starts with a
directed graph and partitions the vertices into strongly-connected
components.  He then removes all edges that connect two vertices in
the same strongly-connected component.  The resulting graph always
seems to be acyclic.

An example is worked out in the figure below.  The original directed
graph is shown on the left.  The vertices $a$, $b$, and $c$ form one
strongly-connected component.  The single vertex $d$ forms a second
strongly-connected component.  Math Moose removes the edges $a
\rightarrow b$, $b \rightarrow c$, and $c \rightarrow a$, since these
edges connect vertices in the same strongly-connected component.  The
resulting graph is shown on the right.  Note that this graph is
acyclic.

\medskip
\centerline{\resizebox{!}{1.5in}{\includegraphics{figures/scc}}}

Use proof by contradiction to show that for every directed graph,
application of Math Moose's procedure gives a directed acyclic graph.

\solution{
\begin{proof}
Let $G = (V,E)$ be an arbitrary directed graph.  Let $G' = (V,E')$ be
the directed graph that remains after we remove all edges that connect
two vertices in the same strongly-connected component.

The proof is by contradiction.  Suppose that $G'$ is not acyclic.
Then let $u$ and $v$ be consecutive nodes in a directed cycle.  There
is a path from $u$ to $v$ consisting of a single edge.  There also is
a path from $v$ to $u$, because the nodes are in a cycle.  Since every
edge in $G'$ is also in $G$, these same two paths exist in the
original graph $G$.  Therefore, $u$ and $v$ are in the same
strongly-connected component of $G$.  But then the edge from $u$ to
$v$ should have been removed during the construction of $G'$.  Since
the the edge was not removed, we have a contradiction.  Therefore,
$G'$ is acyclic.
\end{proof}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\examonly{\newpage}

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


\problem

Use induction to prove that whenever $n$~is a natural number,
\[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2. \]


\solution{
Base Case:  $n = 0 $

The left side is an empty sum, so $0 = \left(\frac{0 \cdot 1}{2}\right)^2 = 0$.

Inductive Step:   Show that $P(n)  \rightarrow P(n+1)$.

By the inductive hypothesis, we assume that 
 \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \]

\begin{eqnarray*}
1^3 + 2^3 + \ldots + n^3 + (n+1)^3 \\
&= &\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\\
&= &\frac{n^2(n+1)^2 + 4(n+1)(n+1)^2}{4}\\
&= &\frac{(n^2+4n+4)(n+1)^2}{4}\\
&= &\left(\frac{(n+1)(n+2)}{2}\right)^2\\
\end{eqnarray*}

And our hypothesis is proved.

{\bf Common errors }

The most common error  was to assume that the hypothesis was
true, and then to prove it by reducing both sides of the equation 
to something that is obviously equal.  This is not a good proof 
technique.

\begin{eqnarray*}
1^3 + 2^3 + \ldots + n^3 + (n+1)^3  &=& \left(\frac{(n+1)(n+2)}{2}\right)^2 \\
\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3  &=& \left(\frac{(n+1)(n+2)}{2}\right)
^2 \\      
\frac{n^2(n^2+2n+1)}{4} + n^3 + 3n^2+ 3n +1 &=& \frac{(n^2+3n+2)^2}{4} \\
\frac{(n^4 +2n^3 +n^2) + (4n^3 + 12n^2 + 12n + 4)}{4} &=& 
\frac { n^4 +3n^3 + 2n^2 + 3n^3 +9n^2 +6n +2n^2 + 6n +4}{4} \\
\frac{n^4 + 6n^3 +13n^2 +12n + 4}{4} &=& 
\frac{n^4 + 6n^3 +13n^2 +12n + 4}{4} \\
\end {eqnarray*}


A technique which is similar but which is not at all correct is to 
start with the equation you wanted to
prove (ie, $f(n)=g(n)$) and then perform the same operations on both sides
of the equation until they're equal.  
\begin{eqnarray*}
n^2+3n+1 &= &n^2+3n+1\\
3n+1 &= & 3n+1\\
1 &= & 1\\
\end{eqnarray*}

This is OK for a quick
check, but does not quite work as a proof, since it is possible to
get equality at the end even if the starting sides of the
equation were not equal. For example
\begin{eqnarray*}
n^2+3n+1 &= &2n^2+5n+8\\
0 \cdot (n^2+3n+1) &= & 0 \cdot (2n^2+5n+8)\\
0 & = & 0\\
\end{eqnarray*}


Remember that in an ideal direct proof, each step should follow from
the previous one, until the final step which is what we want to prove.
}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Prove the set identity
\begin{math}
((A-B) \cup (B-A))^{c} = (A^{c} \cup B) \cap (A \cup B^{c})
\end{math}

\solution{
Using the definition of set difference, both of De Morgan's Laws,
and the commutativity of union (in that order):

\begin{tabbing}
$((A-B) \cup (B-A))^{c}$ \= $= ((A \cap B^c) \cup (B \cap A^c))^c$ \\
                         \> $= (A \cap B^c)^c \cap (B \cap A^c)^c$ \\
                         \> $= (A^c \cup B) \cap (B^c \cup A)$ \\
                         \> $= (A^c \cup B) \cap (A \cup B^c)$ \\
\end{tabbing}

Alternatively, one can use the definitions of the operations.  We need
to prove $x$ is in the LHS if and only if it is in the RHS.


$x \in
((A-B) \cup (B-A))^c$ means that $x \notin (A-B) \cup (B-A)$.  This
means that 
$x \notin A-B$ and $x \notin B-A$.  

So consider cases.  If $x \in A$, then certainly $x \in A \cup B^c$.
Furthermore, since by assumption $x \notin A-B$, we must have $x \in
B$.  Thus, $x \in B \cup A^c$.  Putting these together shows $x \in (A
\cup B^c) \cap (B \cup ^c)$.  Now consider the other case.  
If $x \notin A$, meaning $x \in A^c$, then certainly $x \in A^c \cup B$.
Also, (since $x \notin B-A$), we must have $x \notin B$.  That is, $x
\in B^c$.  Therefore, $x \in B^c \cup A$.  Thus, $x \in (A^c \cup B)
\cap (B^c \cup A)$.  

This proves one direction; the other is similar.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Use the following tables to describe the properties of the
various relations and functions.  Write yes or no in each box.  Don't
give proofs (it'd be too hard to squeeze them into the boxes).  {\bf
  Pay careful attention} to the specified domains and ranges.


\begin{problemparts}

\ppart
The following relations: 

\begin{itemize}
\item $R=\{(a,b)\in (\naturals-\{0\})^2 \mid a \mbox{ divides } b \}$
\item $S=\{(X,Y) \in
(2^{\naturals}-\{\emptyset\})^2 \mid X \cap Y \ne \emptyset\}$
\item  $T=\{(x,y) \in \reals\times\reals \mid x+y=0\}$
\end{itemize}
(Recall that antisymmetric means that $a \sim b$ and $b \sim a$
imply $a=b$).

\smallskip

\begin{tabular}{l|c|c|c|c|c|}
relation & reflexive & symmetric & antisymmetric & transitive &
function\\
\hline
$R:\ a \mid b$ &  &         &            &         &     \\
\hline
$S:\ X \cap Y \ne \emptyset$ &  &  &  &  &  \\
\hline
$T:\ x+y=0$ &  &  &  &  &  \\
\hline
\end{tabular}

\solution{
\begin{tabular}{l|c|c|c|c|c|}
relation & reflexive & symmetric & antisymmetric & transitive &
function\\
\hline
$R:\ a \mid b$ & yes & no        &  yes          &   yes      &  no   \\
\hline
$S:\ X \cap Y \ne \emptyset$ & yes & yes & no & no & no \\
\hline
$T:\ x+y=0$ & no & yes & no & no & yes \\
\hline
\end{tabular}
}

\ppart The following functions: 
\begin{itemize}
\item $f:\naturals \rightarrow \naturals,\
f(x)=5x$.
\item   $g: \reals^+ \rightarrow \naturals,\ g(x)=\lfloor x \rfloor$.
\item $h: \reals \rightarrow \reals^{+},\ h(x)=e^x$.   
\end{itemize}
Give an inverse if one exists (under the given domain and range).

\smallskip
\begin{tabular}{l|c|c|c|c|}
function & injective & surjective & inverse\\
\hline
$f(x)=5x$ &        &         &  \\
\hline
$g(x) = \lfloor x \rfloor$ &  &  &  \\
\hline
$h(x)=e^x$ &  &  &  \\
\hline
\end{tabular}


\solution{
\begin{tabular}{l|c|c|c|c|}
function & injective & surjective & inverse\\
\hline
$f(x)=5x$ &    yes    &   no      & none \\
\hline
$g(x) = \lfloor x \rfloor$ & no & yes & none \\
\hline
$h(x)=e^x$ & yes & yes & ln($x$) \\
\hline
\end{tabular}

{\bf Errors:} A common error here was not to pay attention to the
domain and range.  Although $f(x)=5x$ is a bijection from the reals to
the reals, it is not a bijection from the naturals to the naturals
because there is no {\em natural} number that satisfies $5x=1$.
}

\eparts



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Consider the following algorithm, which takes natural numbers
$a$ and $b$, with $b > 0$, and returns an ordered pair of natural numbers.
\begin{tabbing}
else \= else \= else \= else \=\kill
Algorithm Div$(a,b)$\\
\\
if $(a<b)$\\
\> return $(0,a)$\\
else\\
\> $(q,r) \leftarrow $Div$(a-b,b)$\\
\> return $(q+1,r)$\\
\end{tabbing}

\begin{problemparts}
\problempart Prove Div terminates in at most $a + 1$ steps.

\solution{
We use strong induction on $a$.  The inductive hypothesis is
``if Div$(a',b)$
terminates for all $a'<a$, then Div$(a,b)$ terminates''.

Base Case: $a < b$.  Then Div returns immediately (that is, in one step),
which is certainly no more than $a + 1$ steps, since $ a \geq 0$.

Inductive step:  $a \geq b$.  Then $0 \leq a - b < a$, since $b > 0$.
In this case, there is a recursive call Div$(a-b,b)$.  
By the IH, this recursive call returns in at most $a - b +1$ steps.
Since $a - b < a$, this is at most $a + 1$ steps.

{\bf Common errors }

Please note that many people received credit for a base case
of $a=0$, which is actually wrong.  This case is only reached when $a$ is a
multiple of $b$, so the induction doesn't stand, since for cases where $a$
does not divide $b$, no base case has been shown.

We insisted that you use induction for this because any sort of argument
that goes something like ``And then it keeps on subtracting X until...''
is not rigorous.  Such an argument is begging for induction.
}

\problempart
Prove that Div returns the quotient and remainder of $a$ on
division by $b$.

\solution{
Recall that the quotient and remainder of $a$ on division by $b$
are defined to be the unique integers $q$ and $r$ such that
$a = qb + r$ and $0 \leq r < b$.  These integers must exist
by the Division Algorithm.

We use strong induction on $a$.

Base case: $a < b$.  Then Div immediately returns (0, $a$).
Since $a = 0 \cdot b + a$ and $0 \leq a < b$, these are
the quotient and remainder of $a$ on division by $b$.

Inductive step: $a \geq b$.  Then $0 \leq a - b < a$.
In this case, there is a recursive call Div$(a-b,b)$.  
By the IH, this recursive call returns the quotient and remainder
of $a - b$ on division by $b$.  So $a - b = qb + r$ and $0 \leq r < b$.
Then $a = (q + 1)b + r$ and $0 \leq r < b$.
So $q + 1$ and $r$ are the quotient and remainder of $a$ on division by $b$,
and these are returned by Div.
}


\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem

Let $F$ be a function from $A$ to $B$ and let $G=F^{-1}$ be its
inverse relation ($G$ is a relation from $B$ to $A$, but not
necessarily a function).  Prove that $G\circ F$ is an equivalence
relation on $A$.

\solution{
By definition, $x$ is related to $y$ by $G\circ F$ iff there is a $z \in B$ such that
$x$ is related to $z$ by $F$ and $z$ is related to $y$ by $G$.
That is, $z = F(x)$ and $z = F(y)$.
So $x$ is related to $y$ by $G\circ F$ iff $F(x) = F(y)$.

Reflexitivity:  
Let $x \in A$.  Then $F(x) = F(x)$, so $(x, x) \in G\circ F$.

Symmetry:
Let $x, y \in A$ such that $(x, y) \in G\circ F$.
Then $F(x) = F(y)$ (and $F(y) = F(x)$).
So $(y, x) \in G\circ F$.

Transitivity:
Let $x, y, z \in A$ such that $(x, y), (y, z) \in G\circ F$.
Then $F(x) =  F(y)$ and $F(y) = F(z)$.  So $F(x) = F(z)$ and
$(x, z) \in G\circ F$.

One common mistake for this problem was to assume that $G\circ F$
is the identity function.  In general, $G$ is not a function, and
neither is $G\circ F$.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Consider the following algorithm that takes an array (list) $A[1\ldots n]$ of
numbers such that $A[1]<A[2]<\cdots<A[n]$, and a number $q$, and is
supposed to find $q$ if it is present in the list.

\begin{tabbing}
else \= else\= else\= else \=\kill

Find$(A,n,q)$\\
\\
$i \leftarrow 1$\\
$j \leftarrow n+1$\\
While $(j-i > 1)$\\
\> choose some $k$ with $i<k<j$\\
\> if $A[k] \le q$\\
\>  \> $i \leftarrow k$\\
\> else\\
\>  \> $j \leftarrow k$\\
Return $i$
\end{tabbing}

\begin{problemparts}
\ppart prove this function terminates

\solution{
We first prove (by induction on $l$) that after the $l$th pass
through the while loop, $j - i \leq n - l$.

Base Case: $l = 0$.  When we first reach the while loop, $j - i = n$
because we just set $i$ to 1 and $j$ to $n + 1$.

Inductive Step:  By the IH, $j - i \leq n - l$ after the $l$th pass
through the while loop.  During the ($l + 1$)st pass, either $i$ or
$j$ is moved to a value (that of $k$) strictly between their values
from the end of the $l$th pass.  Thus the ($l + 1$)st pass decreases
$j - i$ by at least 1.  So after the ($l + 1$)st pass through the
while loop, $j - i < n - l - 1 = n - (l + 1)$.

The most common error on this part was hand-waving.  Informal descriptions
of the long-term behavior of the algorithm are not considered proofs
by 6.042 standards.  
Since the reader can safely be assumed to accept induction as a valid
proof technique, the above proof {\em at very least} gives the reader
much less room to object to the argument.

The second most common error was to try to prove the desired statement
directly by induction.  This just doesn't work.  If it did, we would
not have introduced the more complicated proof technique that we said
should be used in this case.
}
\end{problemparts}


\begin{problemparts}
\ppart Now suppose that $q=A[r]$ for some $r$. 
State an invariant of the while loop relating
$i,j$, and $r$.  The invariant should be ``obviously provable by
induction'' but you need not prove it.

\solution{
$i \leq r < j$.
}

\ppart Assuming the invariant, prove that Find returns $r$.

\solution{
When the loop terminates, $j - i \leq 1$ ($j \leq i + 1$).
Also, the invariant still holds.
So $i \leq r < j \leq i + 1$.  Since $i$ and $r$ are integers, $i = r$.
Since $i$ is then returned, Find returns $r$.

Surprisingly enough, a number of people didn't even try to make use
of the invariant.  Use of induction was also common.  The invariant
deals with exactly the issues that would otherwise require induction.
This is why the correctness of the invariant would be proven by induction.
Some people apparently didn't read the question and tried to prove the
invariant correct instead of proving that Find returns $r$.
}

\end{problemparts}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems}



\end{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Below is the quiz from fall 2000.



\documentclass[11pt, twoside]{article}
\input{macros-course}
\usepackage{graphicx}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newif\ifspaceout
\spaceoutfalse
\newcommand{\smallspace}{\ifspaceout\vspace{1in}\fi}
\newcommand{\mediumspace}{\ifspaceout\vspace{3in}\fi}
\newcommand{\largespace}{\ifspaceout\vspace{4in}\fi}
\newcommand{\nextproblem}{\ifspaceout\newpage\fi}

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

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

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

\newcommand{\ROT}{\mbox{ROT}}
\newcommand{\FBT}{\mbox{FBT}}
\newcommand{\brep}{\mbox{rot-to-fbt}}
\newcommand{\unrep}{\mbox{fbt-to-rot}}
\newcommand{\nil}{\mbox{\texttt{()}}}
\newcommand{\sz}{\mbox{size}}
\newcommand{\cons}{\mbox{cons}}
\newcommand{\sbtr}{\mbox{subtrees}}
\newcommand{\kcomp}[1]{\bar{#1}}

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

\newcommand{\kpfend}{}

\newcommand{\kskip}[1]{}

\newcommand{\pts}[1]{\relax[#1 points]\enskip\ignorespaces}
\newcommand{\onept}{\relax[1 point]\enskip\ignorespaces}

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

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

\makeatother

\askaboutsolutions

\begin{document}

\handout{practice-quiz1-sol}{Practice Quiz 1 - Solutions}{March 11, 2001}

\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{30} \textbf{Predicates and Quantifiers}

Use the following propositions where the universe of discourse is the
set of all natural numbers:

\begin{eqnarray*}
P(n):& n \hbox{ is a perfect square}\\
Q(n):& n \hbox{ is prime}\\
R(n,m):& n < m\\
S(n,m):& n \hbox{ divides } m\\
T(n,m):& n = m\\
\end{eqnarray*}

Express each of the following statements using quantifiers, logical
connectives, and the propositions listed above, along with variables and
integers.

\begin{problemparts}

\problempart {\bf (5 points)}  4 is a perfect square and 4 is greater than 1.

\solution{ 
\bigskip
{\bf Solution: }
$P(4) \wedge R(1,4)$ 
}
\bigskip

\smallspace

\problempart {\bf (5 points)}  There is a natural number that divides 
all natural numbers.

\solution{ 
\bigskip
{\bf Solution: }
$\exists n \forall m S(n, m)$
}

\bigskip

\smallspace

\problempart {\bf (5 points)} Two natural numbers are equal exactly
when neither is less than the other.

\solution{ 
\bigskip
{\bf Solution: }
$\forall n \forall m T(n, m) \leftrightarrow \neg R(n, m) \wedge
\neg R(m, n)$
}

\nextproblem

\problempart {\bf (5 points)} A natural number $n$ that is greater
than 1 is prime exactly when the only positive natural number less
than $n$ that divides $n$ is 1.

\solution{ 
\bigskip
{\bf Solution: }
$\forall n Q(n) \wedge R(1,n) 
\leftrightarrow [\forall m R(0, m) \wedge R(m, n)
\wedge S(m, n) \rightarrow T(m, 1)]$
}

\smallspace

\problempart {\bf (5 points)} A natural number $n$ is a perfect square
only if there is a positive natural number (strictly) between 1 and
$n$ that divides $n$.

\solution{ 
\bigskip
{\bf Solution: }
$\forall n P(n) \rightarrow [\exists m R(0, m) \wedge R(1, m) 
\wedge R(m, n) \wedge S(m, n)]$
}

\smallspace

\problempart {\bf (5 points)} Given only the statements (a)-(e) above
and the standard rules of propositional and quantifier reasoning, can
you conclude that 4 is not prime?  If not, state a fact you can use
together with the statements (a)-(e) to conclude that 4 is not prime
(your fact should not mention the number 4).  If so, just list which
of the statements (a)-(e) above are necessary.


\solution{
\bigskip
{\bf Solution: }
We can conclude that 4 is not prime, using parts (a), (c), (d), and (e).

Though a structured proof was not required, we provide one.  The
statement from part (c) was necessary so that we can use that if $m_0
> 1$ then $\neg m_0 = 1$.  Parts (d), and (e) are clearly required, and
part (a) is required so that we know 4 is a perfect square and that 4 > 1,
which are required to use the implications from (d) and (e).  Here is the
structured proof:


\begin{tabbing}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\=XXXXXX\=\kill
1.  $P(4) \rightarrow [\exists m R(0, m) \wedge R(1, m) \wedge R(m, 4)
\wedge S(m, 4)]$\>UI, from part (e).\\
2.  $P(4)$\>Simplification, from part (a).\\
3.  $\exists x R(0, x) \wedge R(1, x) \wedge R(x, 4) \wedge S(x, 4)$
\>Modus Ponens, from 1 and 2.\\
4.  $R(0, m_0) \wedge R(1, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)$
\>EI, from 3.\\
5.  $R(1, m_0)$ \>Simplification, from 4.\\
6.  $T(1, m_0) \leftrightarrow \neg R(1, m_0) \wedge \neg R(m_0, 1)$
    \>UI, from part (c).\\
7.  $\neg R(1, m_0) \wedge \neg R(m_0, 1) \leftarrow T(1, m_0)$
    \>Simplification, from 6.\\
8.  $\neg [R(1, m_0) \vee R(m_0, 1)] \leftarrow T(1, m_0)$
    \>DeMorgan's law, from 7.\\
9.  $R(1, m_0) \vee R(m_0, 1)$  \>Addition, from 5.\\
10.  $\neg T(1, m_0)$  \>Modus Tollens, from 8 and 9.\\
11.  $R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)$ \>Simplification,
     from 4.\\
12.  $(R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)) \wedge \neg T(1,
     m_0)$ \>Conjunction, from 10 and 11.\\
13.  $\neg[\neg (R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)) \vee
     T(1, m_0)]$ \>DeMorgan's Law, from 12.\\
14.  $\neg[(R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)) \rightarrow
     T(1, m_0)]$ \>Logical equivalence, from 13.\\
15.  $\exists m \neg [(R(0, m) \wedge R(m, 4) \wedge S(m, 4))
     \rightarrow T(1, m)]$ \>EG, from 13.\\
16.  $\neg \forall m [(R(0, m) \wedge R(m, 4) \wedge S(m, 4)) \rightarrow
     T(1, m)]$ \>Negation rule for quantifiers\\
17.  $Q(4) \wedge R(1,4) \leftrightarrow [\forall m R(0, m) \wedge
     R(m, 4) \wedge S(m, 4) \rightarrow T(m, 1)]$ \>\>UI, from part (d).\\
18.  $\neg (Q(4) \wedge R(1,4))$  \>Modus Tollens, from 15 and 16.\\
19.  $\neg Q(4) \vee \neg R(1,4)$  \>DeMorgan's Law, from 18.\\
20.  $R(1,4)$ \>Simplification, from part (a).\\
21.  QED $\neg Q(4)$  \>Disjunctive Syllogism, from 19 and 20.  
\end{tabbing}}
\nextproblem

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{25} \textbf{Relations}
\begin{problemparts}

For each relation listed in parts (a) through (e) circle {\em all} terms
listed that apply to it.

\problempart {\bf (5 points)}  $A = \{a, b\}, R = \{(a, a), (a, b)\}$.

\solution{ 
\bigskip {\bf Solution: }
This relation is antisymmetric and transitive.
}

\problempart {\bf (5 points)} $aRb$ whenever $a$ and $b$ are students
and either $a = b$ or $a$ has a GPA greater than or equal to that of
$b$.  (You may assume that all students have different GPAs).

\solution{
\bigskip {\bf Solution: }
This relation is reflexive, transitive and antisymmetric, so it is
a partial order.  Furthermore, since any two different students have
different GPAs, they can be compared with $R$.  Therefore, this 
relation is also a total order.
}

\problempart {\bf (5 points)} $aRb$ whenever $a$ and $b$ are real numbers
and $a = b^x$ for some rational number $x$.

\solution{
\bigskip {\bf Solution: }
This relation is not symmetric, since $1 = 4^0$ but $1^x$ is 1 for any 
rational number $x$.  However, it is not antisymmetric since $2 = 4^{.5}$
and $4 = 2^2$.  Thus is is none of these.
}

\problempart {\bf (5 points)}  $aRb$ whenever $a$ and $b$ are rational
numbers and $ab$ is an integer.

\solution{
\bigskip {\bf Solution: }
This relation is not reflexive (for instance, $\neg(.5R.5)$).
Therefore, it is none of these.
}


\problempart {\bf (5 points)} $aRb$ whenever $a$ and $b$ are integers such
that there is a nonnegative integer $k$ such that $3^k | a$ and $3^k | b$
and $3^{k+1}\not|a$ and $3^{k+1}\not|b$.  

\solution{\bigskip
{\bf Solution: }
This relation is essentially just saying that $3$ divides $a$ and $b$
the same number of times.  This is an equivalence relation, since
the same number of times is reflexive, symmetric and transitive.

} \nextproblem


\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{15} \textbf{Directed Graphs}

Recall that a {\em tournament graph} is a directed graph in which
between any two different nodes $a$ and $b$ there is an edge either
from $a$ to $b$ or from $b$ to $a$ but not both, and there are no
other edges in the graph.

For each of the following, answer true or false and give a brief
justification of your answer.

\begin{problemparts}

\problempart{\bf (5 points)} There is no tournament graph on 4 nodes with
an Euler circuit.

\solution{
\bigskip {\bf Solution: }
The claim is true.

In a tournament graph on 4 nodes, every node will have an odd number
(3) of edges, so the degree of every node is odd.  A directed graph
has an Euler circuit only when every node has equal in-degree and
out-degree.  However, if the total degree (in-degree plus out-degree)
is odd, the in-degree and out-degree cannot be equal.  Thus, there is
no Euler circuit.
}

\smallspace

\problempart{\bf (5 points)} There is no tournament graph on 5 nodes
with an Euler circuit.


\solution{
\bigskip {\bf Solution: }
The claim is false.

An example is the graph on five nodes $a, b, c, d, e$ where the
edges are $(a,b),\, (b,c),\, (c,d),$ $(d,e),\, (e,a),\, (a,c),\,(c,e),\,
(e,b),\, (b,d),\,(d,a).$  The edges in this order make an Euler circuit.  
}

\smallspace

\problempart{\bf (5 points)} There is no tournament graph on 225 nodes with
an Euler circuit.

\solution{
\bigskip {\bf Solution: }
The claim is false.

The complete graph on 225 nodes has an Euler circuit, since every node
has degree 224, which is even.  Since an Euler circuit contains every
edge, all we have to do to construct a 225-node tournament graph with
an Euler circuit is take the Euler circuit on $K_{225}$ and choose a
direction, then include every edge in our 225-node tournament graph in
the direction it appears in the Euler circuit.  This will be a
tournament graph, since every two nodes are connected and every edge
is directed.

}

\nextproblem

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{8} \textbf{Structured Reasoning}

For this proof, fill in the predicate and quantifier rules used for
each step denoted with a *, and say which statements they are based on.


\begin{tabbing}
Given: $\forall x \exists y [Q(x, y) \vee R(x, y)]$\\
Prove: $\forall x [\exists y Q(x,y) \vee \exists y R(x,y)]$\\
Proof:\\
*\=XX\=*\=XX\=*\=XXXXXXXXXXXXXXXXXXXXXXXXX\=\kill
\>1.  Let $x_0$ be  arbitrary.\\         
\>2.  $\exists y [Q(x_0, y) \vee R(x_0, y)]$
\>\>\>\>\>Universal Instantiation, from Given\\
\>3.  $Q(x_0, y_0) \vee R(x_0, y_0)$
\>\>\>\>\>Existential Instantiation, from 2.\\
\>4.  $\exists y Q(x_0, y) \vee \exists y R(x_0, y):$\\
\>\>\>4.1.  case $i$:  Assume $Q(x_0, y_0)$.\\
\>\>\>\>*4.1.1.  $\exists y Q(x_0, y)$
\>\>\underline{\hspace{2in}}\\
\>\>\>\>*4.1.2.  $\exists y Q(x_0, y) \vee \exists y R(x_0,y)$
\>\>\underline{\hspace{2in}}\\
\>\>\>4.2.  case $ii$:  Assume $R(x_0, y_0)$.\\
\>\>\>\>\>4.2.1.  $\exists y R(x_0, y)$\\
\>\>\>\>\>4.2.2.  $\exists y Q(x_0, y) \vee \exists y R(x_0,y)$\\
\>\>*4.3. QED $\exists y Q(x_0, y) \vee \exists y R(x_0, y)$
\>\>\>\>\underline{\hspace{2in}}\\
*5. QED $\forall x [\exists y Q(x,y) \vee \exists y R(x,y)]$
\>\>\>\>\>\>\underline{\hspace{2in}}
\end{tabbing}

\solution{ {\bf Solution:}
4.1.1:  Existential Generalization, from 4.1

4.1.2:  Addition, from 4.1.1

4.3:  Proof by cases, from 3, 4.1.2, and 4.2.2

5:  Universal Generalization, from 1 and 4.3
}

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 5 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{32} \textbf{Proof Comprehension}

For each of the following proofs, determine whether it is valid or
invalid.  If it is valid, say so.  If it is invalid, what about the
proof is incorrect?  (NOTE:  If you say a proof is valid, feel free
to give some explanation for why you think that proof is valid.  This
may give you some partial credit if you are incorrect.)

\begin{problemparts}

\problempart {\bf (8 points)}  

\begin{tabbing}
Theorem: 2 = 1.  \\
Proof:\\
1.  Assume $2 = 1$.\\
2.  $x^2 + 2 = x^2 + 1$.\\
3.  $2x dx = 2x dx$.  (differentiating both sides)\\
4.  $2 = 2$  (dividing both sides by $x dx$)\\
5.  Therefore, $2 = 1$ (QED)
\end{tabbing}

\solution{
\bigskip {\bf Solution: }
Step 5 is invalid.  After step 4 we have proven that $(2 = 1) \rightarrow
(2 = 2)$.  This is an implication, and is true even if $2 \neq 1$.  So
we can't conclude that $2 =1$.  This is known as the fallacy of affirming
the conclusion.
}

\smallspace

\problempart {\bf (8 points)}  

\begin{tabbing}
Theorem:  All rational numbers $x$ greater than
or equal to 1 are such that $x \leq 2^x$.\\
Proof:  Let $P(n)$ be the statement ``$n \leq 2^n.$''\\
1.  We know that $1 \leq 2^1 = 2$.  Therefore, $P(1)$.\\
2.  Assume $P(n)$ where $n \geq 1$.\\
3.  Then, $n \leq 2^n$\\
4.  Adding $1$ to both sides, we get $n + 1 \leq 2^n + 1$\\
5.  Substituting that $1 \leq n$, we get $n + 1 \leq 2^n + n$.\\
6.  Substituting from step 3 into the RHS of step 5, we get $n+1 \leq
    2^n + 2^n$\\
7.  Simplifying, we get $n+1 \leq 2^{n+1}$.\\
8.  Thus, $P(n+1)$.  Therefore, by induction, $\forall n P(n)$.
\end{tabbing}

\solution{ 
\bigskip {\bf Solution: }
This proof is invalid.  Step 7 is invalid, since $\forall n
P(n)$ would be a statement about the rational numbers (since that was
the statement of the theorem), but induction allows us to conclude only
that $\forall n \in \naturals \; P(n)$.  }

\nextproblem

\problempart {\bf (8 points)} 

Theorem: If $G$ is a finite graph with
positive integer-weighted edges that has a spanning tree, it has a 
minimal spanning tree (a spanning tree $T$ such that the
sum of the weights of the edges in $T$ is as small as it could be
for any spanning tree).

Proof:  Every spanning tree of $G$ has a total weight $w$ which is
non-negative integer.  Therefore, the set of possible total weights of
spanning trees is a subset of the non-negative integers.  By the
well-ordering property, since there is a spanning tree, there must be
a least weight of a spanning tree, and therefore there must be a
spanning tree that has that weight.  Thus, there is a minimal spanning
tree.

\solution{
\bigskip {\bf Solution: }
This proof is valid.  
}

\problempart {\bf (8 points)} 

Theorem: There are infinitely many prime numbers.

Proof: Let $S$ be the set of all prime numbers.  Now let $k = 1 +
\prod_{p \in S} p$.  Note that $k$ is not divisible by any $p$ in $S$
since the remainder when dividing by $p$ would be 1.  Furthermore,
notice that if $p$ is any element of $S$ then $k = 1 + \prod_{q \in S}
q \geq 1 + p > p$.  But this is a contradiction.  Therefore, there
must be infinitely many prime numbers.

\solution{
\bigskip {\bf Solution: }
The proof is sloppy enough to be considered invalid.

This is basically just like the classical proof that there are
infinitely many primes, but it's sloppily done.  Here are the two
significant problems with the proof, from minor objections to major
ones.

1.  The author never explains why what has been derived about $k$
causes something new to be prime.  It should be mentioned that either
$k$ must be prime, or it must contain a prime factor not in $S$, which
is what creates the contradiction.  This is a serious omission, but
since this omission could just be filled in, it is not something bad
enough to make the proof invalid.

2.  Most importantly, the author never includes the assumption that
$S$ is finite.  If $S$ is infinite, the whole argument falls apart
since $k$ would not be a number and so everything that's reasoned
about $k$ would be invalid.  This is serious enough that the proof
is not valid without it.

}

\nextproblem

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 6 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{30} \textbf{Hamiltonian Circuits}
\begin{problemparts}


In this problem you will prove that for any positive integer $n$, any 
$2n$ by $2n$ grid graph has a Hamiltonian circuit.  

An $n$ by $m$ grid graph is made up of vertices described as pairs of 
integers $(x, y)$ where $0 \leq x < n$ and $0 \leq y < m$.  There is
an edge between two vertices if their $x$-coordinates differ by 1 or
if their $y$-coordinates differ by 1 but NOT if both differ by 1.

So, for example, there would be edges between the vertices $(2,3)$ and
$(3,3)$ but not between $(2,3)$ and $(3,2)$.

\problempart {\bf (4 points)}  Draw a 4 by 4 grid graph.  Label vertices
$(1, 3)$, $(2, 2)$, and $(2, 3)$.  

\solution{
\bigskip
{\bf Solution: }
\begin{center}
{\includegraphics[height=3.0in]{figures/quiz1p6a}}
\end{center}
}

\smallspace

\problempart {\bf (10 points)} Prove that the chromatic number of any
$m$ by $n$ grid graph is 2 (for $m, n > 1$).

\solution{
\bigskip {\bf Solution: } To prove that the chromatic number of an $m$
by $n$ grid graph is 2, we must show that it cannot be colored with 1
color, and that it can be colored with 2 colors.

Since $m,n > 1$, there is an edge from $(0,0)$ to $(0, 1)$, so the
graph cannot be 1-colored, since these two vertices must have different
colors.

To color the graph with 2 colors, simply let all vertices $(x,y)$
where $x + y$ is even be colored white, and let all vertices where
$x+y$ is odd be colored black.  Since nodes are only adjacent to other
nodes where $x$ or $y$ differs by 1, but not both, we see that every
node adjacent to $(x,y)$ is such that the sum of that nodes
coordinates is either $x+y-1$ or $x+y+1$.  Thus, any white node is
adjacent only to black nodes, and vice versa.  

}

\nextproblem

\problempart {\bf (16 points)} Prove by induction that any $2n$ by
$2n$ grid graph has a Hamiltonian circuit for $n \geq 1$.  (Other
proof methods will not get credit) Note: this question does not have
anything to do with the question in part (b).

\solution{
\bigskip {\bf Solution: }
Let $P(n)$ be the statement ``Any $2n$ by $2n$ grid graph has
a Hamiltonian circuit.''

$P(1)$:  Any 2 by 2 grid graph is just a square.  The square itself
is a circuit, and it touches all the nodes.  Thus, it is a Hamiltonian
circuit.

Assume $P(n)$.  Let $G$ be a $2(n+1)$ by $2(n+1)$ grid graph.  We
construct a Hamiltonian circuit for $G$ as follows.  First, let the
subgraph on all the vertices with $x < 2n$ and $y < 2n$ be called
$H$.  $H$ is a $2n$ by $2n$ grid graph, so it has a Hamiltonian circuit.

Start at vertex $(0, 2n+1)$ and continue straight to $(2n+1, 2n+1)$
and then down to $(2n+1, 0)$, then to $(2n, 0)$.  Now, since we know
there's a Hamiltonian circuit in $H$, pick one.  $H$ must include
the edge from $(2n-1, 0)$ to $(2n-1, 1)$ since in $H$, vertex $(2n-1, 0)$
has degree 2.  

Now we continue our path to vertex $(2n-1, 0)$ and through the circuit 
for $H$ in the direction of $(2n-2, 0)$.  After visiting all the nodes
in $H$, this will return us to $(2n-1, 1)$.  From there we continue to 
$(2n, 1)$ and up to $(2n, 2n)$ and back to $(0, 2n)$ and we close the
circuit by going back to $(0, 2n+1)$.  

Thus, $P(n+1)$.  By induction, if $n$ is an integer $\geq 1$ then
Any $2n$ by $2n$ grid graph has a Hamiltonian circuit.
}

\nextproblem

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 7 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{40} \textbf{State Machines and Invariants}
\begin{problemparts}

Consider the following algorithm, that, given a number, produces
the prime factorization of that number.  The prime factorization of
a number is a list of all primes that divide that number, where
primes may be listed multiple times if they divide the number multiple
times.  The product of all the numbers in the list should be equal
to the original number.

Assume that  Append ($List, i$) takes a list and adds the element
$i$ to the beginning of it.  Assume that $()$ refers to the list
with no elements.

\begin{tabbing}
FactorPrime $(n \in {\mathbb N})$:\\
1.  $i := 2.$\\
2.  $List := ().$\\
3.  $m := n.$\\
4.  \=IF \=$m = 1$ THEN\\
       \>\>FactorPrime$(n)$: = $List$.\\
5.    IF   $i | m$ THEN\\      
       \>\>Append ($List, i$).\\
       \>\>$m := m/i$.\\
    \>ELSE\\
       \>\>$i := i+1$.\\
6.  Go to step 4.\\
\end{tabbing}

\problempart {\bf (10 points)}  Represent this algorithm as a state
machine.

\solution{
\bigskip{\bf Solution:}

The states of the machine can be described by 

$$Q = \{(i, m, List)| i, m \in {\Bbb Z}, List \hbox{ is a list of integers}\}$$

The starting state on input $n$ is $(2, n, ())$.  The transitions
are described by:

\begin{tabbing}
$\delta(i, m, List)$\= = nothing if $m=1$,\\
                    \> = $(i, m/i, $Append$(List,i))$ if $i|m$, or\\
                    \> = $(i+1, m, List)$ otherwise.
\end{tabbing}
}

\nextproblem

\problempart {\bf (10 points)} Using an invariant, prove that if the
algorithm ever gets to the point where $m = 1$, then the list is a
factorization (not necessarily a prime factorization) of its input
$n$.

\solution{
\bigskip{\bf Solution:}
The following is the invariant we will use.

$P(i,m,List)$: ``The product of all the numbers in $List$ and the
number $m$ equals $n$.''

To prove that this is an invariant, we note that since the start state
of the state machine is $(2, n, ())$, the product of all the numbers
in $List$ and $m$ is just $m$, which is $n$.

Now suppose that $P(i,m,List)$ is true.  We wish to prove that
$P(\delta(i,m,List))$ is true.  We proceed by cases.

{\bf Case 1:}  $i|m$.  Then, $\delta(i,m,List) = (i, m/i, Append(List,i))$.

Note that if the product of all numbers in list was $k$, the
product of all numbers in Append($List, i$) would be $ki$.  Therefore,
since $km = n$ then $(ki)(m/i) = km = n$ also, so $P(\delta(i,m,List))$ is
true.

{\bf Case 2:}  $i\not|m$.  Then, $\delta(i,m,List) = (i+1,m,List)$.

Since $m$ and $List$ are unchanged, the invariant continues to hold.

Therefore, $P(i,m,List)$ is an invariant of our state machine.  So, if $m=1$,
then the product of all the numbers in $List$ must equal $n$.  Thus,
$List$ is a factorization of $n$.
}



\mediumspace

\problempart {\bf (10 points)}  Prove that the list
never contains any numbers that are not prime.  

\solution{
\bigskip{\bf Solution:}
The following is the invariant we will use.

$R(i,m,List)$ = ``$List$ contains no non-prime numbers, and no
        numbers (other than 1) less than i divide $m$."

In the start state, the list contains no numbers at all so it cannot contain
any non-prime numbers.  Finally, there are no numbers less than 2
other than 1, so $R(2,n,())$ is true.

Now suppose we know that $R(i,m,List)$ is true.  We will prove that
$R(\delta(i,m,List))$ is true.  There are two cases:

{\bf Case 1:}  $i|m$.  Then, $\delta(i,m,List) = (i, m/i, Append(List,i))$.

If no numbers less than $i$ divide $m$, then no
numbers less than $i$ divide $m/i$ since $m/i$ divides $m$.

We must also prove that Append($List, i$) contains no non-prime
numbers. The only element in Append($List, i$) that is not in $List$
(which we know contains no non-prime numbers) is $i$.  Thus, we are
asked to prove that $i$ is prime, which we do by contradiction.
Suppose $i$ is not prime.  Then $i$ has a prime factor smaller than
$i$ other than 1: call it $h$.  Since $h|i$ and $i|m$ we know that
$h|m$.  But, since $R(i,m,List)$ is assumed, there can be no numbers
smaller than $i$ other than 1 which divide $m$.  Thus, by
contradiction, we see that $i$ is prime.  Therefore,
$R(\delta(i,m,List))$.

{\bf Case 2:}  $i\not|m$.  Then, $\delta(i,m,List) = (i+1,m,List)$.

Since $List$ did not change, it cannot contain any non-prime
numbers, since $R(i,m,List)$ is true.  

Also, we must verify that no numbers less than $i+1$ other than 1
divide $m$.  The only number less than $i+1$ which is not less than
$i$ is $i$ itself.  However, we know that $i$ does not divide $m$.

Therefore, $R(\delta(i,m,List)$.

Since $R$ is an invariant, it is clear that in particular, $List$
never contains any numbers that are not prime.

}

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

\solution{
\bigskip{\bf Solution:}
The following is a termination function:  

$f(q) = n+m-i$. 

This function is always decreasing because either type of transition
decreases it: one increases $i$, while the other decreases $m$.

This function is always an integer, since $n$ and $i$ are clearly
always integers, and $m$ is divided by $i$ only when $i|m$, so $m$ is
also always an integer.

By our invariant from part (b), we know that $m | n$, so therefore $m
\leq n$.  We now prove that $i \leq n$.  Suppose not.  Then, since $i
> m$, by our invariant from part (c), we know that there is no prime
less than $i$ that divides $m$ other than 1, so $m$ must be 1.
(Otherwise, $m$ would have a prime factor which would be less than or
equal to itself, and therefore less than $i$) But then since $m=1$ the
previous state must have been $(i, i, List)$ for some $List$ (it could
not have been $(i-1, 1, List)$ since there are no transitions when
$m=1$).  Thus, $i | n$ which implies that $i \leq n$.

Thus, $f(q)$ is always positive.  It achieves its lowest value when
$m$ is as small as possible and $i$ is as large as possible.  Since
$m \geq 1$ and $i \leq n$, this shows that $f(q) \geq 1$.  

By the termination theorem, the algorithm terminates.
}



\nextproblem


\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 8 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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.  }








\end{problems}

\end{document}
