\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}
\begin{document}
\newcommand{\solution}[1]{}
%\renewcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}

\pset{5}{October 8, 1999}{start of tutorial, October 14, 1999}
\textbf{Reading} The Rosen text, \S 7.5, 8.1-2, 8.5; S99 Handout 12 \S 5; 
F97 Lecture Notes 6

{\large
Remember to include a \textbf{collaboration statement} on the front page
of your solutions (see Handout 2, \emph{Course Information}).}

Note: None of these problems requires a lot of writing.  Consider this
when writing up your solutions.

\begin{problems}
\problem \textbf{Integer Multiplication}
Consider the following procedure to compute the product
of positive integers $x$ and $y$.
\begin{itemize}
\item Do the assignment $a := x$.
\item Do the assignment $b := y$.
\item Repeat the following steps:
\begin{itemize}
\item If $b = 1$ \textbf{return} $a$ and halt.
\item Do the assignment $a := a + x$
\item Do the assignment $b := b - 1$
\end{itemize}
\end{itemize}
\renewcommand{\theenumi}{(\roman{enumi})}
\begin{enumerate}
\item Model the procedure with a state machine. 
\item Formulate an invariant relating $x$, $y$, $a$, and $b$,  which
holds at the top of the loop. Your invariant should imply that upon
termination, $a = xy$.
\item Prove that the invariant holds. 
\item Argue that the process terminates. 
\end{enumerate}
\renewcommand{\theenumi}{(\arabic{enumi})}

\solution{
(i). The states Q can be represented as tuples $(x, y) \subset (\mathbb{N} \times \mathbb{N}$). \\
The initial state $q_0$ is $(x, y)$. 
There is only one transition: $(a,b) \rightarrow (a+x, b-1)$. 
The terminating condition is $b = 1$, and the machine outputs $a$. \\
(ii). The invariant is expressed by the predicate $P(\cdot)$, which takes
a state of the machine as its argument: \\
$P(a,b)$ = ``$a + x(b-1) = xy$'' \\
Note that if $b = 1$ and $P(a,b)$, then $a + x(1-1) = xy \Rightarrow a = xy$. \\
(iii). $P(q_0)$ holds, since $x + x(y-1) = x + xy - x = xy$. 
If $(q, q')$ is a valid transition, we will show that $P(q) \Rightarrow P(q')$. 
For any state $q = (a, b)$, $q'$ will be a state following $q$ iff $q' = (a+x, b-1)$.
If we assume that $P(q)$ holds, then $a + x(b-1) = xy \Rightarrow a + xb - x = xy
\Rightarrow a+(x-x)+xb-x=xy \Rightarrow (a+x)+x(b-2)=xy$, which is $P(q')$. \\
(iv). The process terminates when $b = 1$. Since $b$ begins as a positive integer and 
decreases by one with each transition, it must reach 1.
}

\problem \textbf{Modular Exponentiation} \\
Consider the following procedure to compute $a^b \bmod n$.
\begin{itemize}
\item Let $\langle b_k, b_{k-1}, \ldots, b_0\rangle$ be the binary representation of $b$.
\item Do the assignment $c := 1$.
\item Do the assignment $d := a \bmod n$.
\item Do the assignment $i := k$.
\item Repeat the following steps:
\begin{itemize}
\item if $i = 0$ \textbf{return} $d$ and halt.
\item Do the assignment $i := i-1$.
\item Do the assignment $c := 2c$.
\item Do the assignment $d := (d \cdot d) \bmod n$.
\item if $b_i = 1$
\begin{itemize}
\item Do the assignment $c := c+1$.
\item Do the assignment $d := (d \cdot a) \bmod n$.
\end{itemize}
\end{itemize}
\end{itemize}

\renewcommand{\theenumi}{(\roman{enumi})}
\begin{enumerate}
\item Model the procedure with a state machine. 
\item Notice that at the begining of every iteration 
the binary representation of $c$ 
is $\langle b_k, b_{k-1}, \ldots, b_i \rangle$.
Formulate an invariant relating $a$, $b$, $c$, $d$, $i$, and $n$,  which
holds at the top of the loop. Your invariant should imply that upon
termination, $d = a^b \bmod n$.
\item Prove that the invariant holds. 
\end{enumerate}
\renewcommand{\theenumi}{(\arabic{enumi})}
\solution{
(i). The states $Q$ can be represented as triples $(c, d, i) \subset
(\mathbb{N} \times \mathbb{N}\times \mathbb{N}$). The initial state
$q_0$ is $(1,a\bmod n,k)$.  
There are two possible transitions: if $b_{i-1} = 0$,
then $(c,d,i) \rightarrow (2c, d^2 \bmod n, i-1)$, else $(c,d,i)
\rightarrow (2c+1, d^2a \bmod n, i-1)$.  The terminating condition is
$i = 0$, and the machine outputs $d$. \\
(ii). The invariant is expressed by the predicate $P(\cdot)$, which
takes a state of the machine as its argument: \\ $P(c,d,i)$ = ``$d =
a^c \bmod n \wedge c = \langle b_k, b_{k-1}, \ldots, b_i \rangle$'' \\
Note that if $i = 0$ and $P(c,d,i)$, then $c = b$, and therefore $d =
a^b \bmod n$. \\
(iii). $P(q_0)$ holds, since $d = a \bmod n = a^1 \bmod n = a^c \bmod n$, 
and $c = 1 = b_k$
($b_k$ must be 1, as it is the most significant bit).  If $(q, q')$ is
a valid transition, we will show that $P(q) \Rightarrow P(q')$.  For
any state $q = (c,d,i)$, $q'$ will be a state following $q$ iff either
$b_i-1 = 0$ and $q' = (2c, d^2 \bmod n, i-1)$ or $b_i-1 = 1$ and $q'=(2c+1,
d^2a \bmod n, i-1)$.  If we assume that $P(q)$ holds, \emph{i.e.} $d_0
= a^{c_0} \bmod n$ and $c_0 = \langle b_k, b_{k-1}, \ldots,
b_{i_0}\rangle$ then there are two cases to consider. In the case
$b_{i_0-1} = 0$, we have $d = d_0 \cdot d_0 \equiv a^{c_0} \cdot
a^{c_0} \equiv a^{2c_0} \equiv a^c \pmod n$ and $c = 2c_0 = \langle
b_k, \ldots, b_{i_0}, 0 \rangle$, which is $P(q')$. In the case that
$b_{i_0-1} = 1$, we have $d = d_0 \cdot d_0 \cdot a \equiv a^{c_0}
\cdot a^{c_0} \cdot a \equiv a^{2c_0+1} \equiv a^c \pmod n$ and $c =
2c_0+1 = \langle b_k, \ldots, b_{i_0}, 1 \rangle$, which is $P(q')$. 
}

\problem \textbf{The Touring Knight} \\
%% Remove the Rosen cite, since the last problem is an odd exercise %%
A knight is a chess piece that can move either two spaces horizontally
and one space vertically or one space horizontally and two spaces
vertically.  That is, a knight on square $(x, y)$ can move to any of the
eight squares $(x \pm 2, y \pm 1), (x \pm 1, y \pm 2)$, if these squares
exist on the chessboard (which is normally 8 $\times$ 8).

A knight's tour is a sequence of legal moves by a knight starting at
some square and visiting each square exactly once.  A knight's tour is
called reentrant if there is a legal move that takes the knight from
the last square of the tour back to where the tour began.  We can
model knight's tours using the graph that has a vertex for each square
on the board,with an edge connecting two vertices if a knight can
legally move between the squares represented by these vertices.
\begin{problemparts}

\problempart 
Show that finding a reentrant knight's tour on an $m
\times n$ chessboard is equivalent to finding a Hamilton circuit on
the corresponding graph. 

\solution{In a Hamiltonian circuit, we need to visit each vertex once
moving along the edges and returning to the starting point. A
reentrant knight's tour is precisely such a circuit, since we visit
each square once, making legal moves, and return to the starting
point.}

\problempart 
Show that the graph representing the legal moves of a
knight on a $m \times n$ chessboard, wherever $m$ and $n$ are
positive integers, is bipartite.

\solution{Each square of the board can be thought of as a pair of
integers $(x,y)$. Let $A$ be the set of squares for which $x+y$ is
odd, and let $B$ be the set of square for which $x+y$ is even. This
partitions the vertex set of the graph representing the legal moves of
a knight on the board into two parts. Now every move of the knight
changes $x+y$ by an odd number -- either $1+2=3$, $2-1=1$, $1-2=-1$,
or $-1-2=-3$. Therefore every edge in this graph joins a vertex in $A$
to a vertex in $B$. Thus the graph is bipartite.}

\problempart Deduce that there is no reentrant knight's tour on an $m
\times n$ chessboard when $m$ and $n$ are both odd. (\emph{Hint:}
Problem Set 4, problem 7.)

\solution{Since there are $mn$ squares on the $m \times n$ board, if
both $m$ and $n$ are odd, there are an odd number of squares. Since by
part (b), the corresponding graph is bipartite, from PS 4, problem 7,
we know that it has no cycle of odd length, \emph{i.e.} it has no
Hamilton circuit (since there are an odd number of nodes). Hence,
there is no reentrant knight's tour.}

\end{problemparts}

\problem \textbf{Decision Trees} \\ How many weighings
of a balance scale are needed to find a counterfeit coin among 8 coins
if the counterfeit coin is either heavier or lighter than the others?

\solution{
Decision tree theory applied naively say that at least
$\lceil \log_3 8 \rceil = 2$ weighings are needed, but in fact at least
3 weighings are needed. To see this, consider what the first weighing
might accomplish. We can put 1, 2, or 3 coins in each pan for the
first weighing (no other arrangement will yield any information at
all). If we put on or two coins in each pan, and if the scale
balances, then we only know that the counterfeit is among the six or
four remaining coins. If we put 3 coins in each pan and if the scale
does not balance, then essentially all we know is that the counterfeit
coin is among the six coins involved in the weighing. In every case,
we have narrowed the search to more than 3 coins, so one more weighing
cannot find the counterfeit (there being only three possible outcomes
of one more weighing). }

\problem \textbf{Euler Circuits} \\ Show that a
directed multigraph having no isolated vertices has an Eulerian
circuit if and only if the graph is weakly connected and the in-degree
and out-degree of each vertex are equal.

\solution{First suppose that the directed multigraph has an Euler
circuit. Since the circuit provides a path from every vertex to every
other vertex, the graph must be strongly connected (and hence also
weakly connected). Also, we can count the in-degrees and out-degrees
of the vertices by following the circuit; as the circuit passes
through a vertex, it adds one to the count of both the in-degree (as
it comes in) and the out degree (as it leaves). Therefore the two
degrees are equal for each vertex. Conversely, suppose that the graph
meets the conditions stated. Then we can proceed as in the proof of
Theorem 1 (Rosen p.478) and construct an Euler circuit. }

\problem \textbf{Rooted Spanning Trees} \\
A \textbf{directed, rooted spanning tree} of a digraph is a
rooted tree whose edges are from the digraph with the property 
that every vertex of
the digraph is reachable by a directed path from the root of the tree.
Show that
a connected directed graph in which each vertex has the same in-degree
and out-degree has a rooted spanning tree. (\emph{Hint:} Use an Euler
circuit.)

\solution{By the previous problem, there is an Euler circuit in the
directed graph. We follow $C$ and delete from the directed graph every
edge whose terminal vertex has been previously visited in $C$. We
claim that the edges that remain in $C$ form a rooted tree. Certainly,
there is a directed path from the root to every other vertex, since we
only deleted edges that allowed us to reach vertices we could already
reach. Furthermore, there can be no simple circuits, since we removed
every edge that would have completed a simple circuit.}

\problem \textbf{Triangle Inequality} \\ 
Let $T_1$ and $T_2$ be spanning trees of a graph. The
\textbf{distance} between $T_1$ and $T_2$ is the number of edges in
$T_1$ and $T_2$ that are not common to $T_1$ and $T_2$. Suppose that
$T_1, T_2$ and $T_3$ are spanning trees of the simple graph $G$. Show
that the distance between $T_1$ and $T_3$ does not exceed the sum of
the distance between $T_1$ and $T_2$ and the distance between $T_2$
and $T_3$.

\solution{Suppose that $T_1$ contains $a$ edges that are not in $T_2$,
so that the distance between $T_1$ and $T_2$ is $2a$. Suppose that
$T_2$ contains $b$ edges that are not in $T_3$, so the distance
between $T_2$ and $T_3$ is $2b$. Now at worst, the only edges that are
in $T_1$ and not in $T_3$ are those $a+b$ edges that are in $T_1$ and
not in $T_2$, or in $T_1$ and $T_2$ but not in $T_3$. Therefore the
distance between $T_1$ and $T_3$ is at most $2(a+b)$.}

\problem
\textbf{Minimum Spanning Trees} \\
A minimum spanning tree in a connected weighted graph $G$ is a
spanning tree in $G$ with the property that no other spanning tree in
$G$ has a lower total weight. Show that an edge with smallest weight
in a connected weighted graph must be part of any minimum spanning
tree.

\solution{
Suppose that an edge $e$ with smallest weight is not included in some
minimal spanning tree; in other words, suppose that the minimum
spanning tree $T$ contains only edges with weights larger than that of
$e$. If we add $e$ to $T$, then we will obtain a graph with exactly
one simple circuit, which contians $e$. We can then delete some other
edge in the circuit, resulting in a spanning tree with weight strictly
less than that of $T$ (since all the other edges have larger weight
than $e$ has). This is a contradiction to the fact that $T$ is a
minimum spanning tree. Therefore, an edge with smallest weight must be
included in $T$.}

\end{problems}
\end{document}	


