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

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{5, Mon}                    % !! start the paper

\begin{problem} 
By now you are very familiar with the
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/}{6.042 icon} that
appears on every lecture slide and course webpage.  This icon is a picture
of a game called the \textbf{Fifteen Puzzle}.  In this problem you will
establish a basic property of the Fifteen Puzzle using the method of
invariants, and, if this exercise works as planned, you will come to
appreciate why this icon was chosen as the 6.042 logo.

The Fifteen Puzzle consists of sliding square tiles numbered $1,\dots,15$
held in a $4\times4$ frame with one empty square.  Any tile adjacent to
the empty square can slide into it.

The standard initial position is
\[\begin{array}{|c|c|c|c|}
\hline 1 & 2 & 3 & 4\\
\hline 5 & 6 & 7 & 8\\
\hline 9 & 10 & 11 & 12\\
\hline 13 & 14  & 15 &  \\
\hline
\end{array}\]
We would like to reach the target position (known in my youth as ``the
impossible'' --- ARM):
\[\begin{array}{|c|c|c|c|}
\hline 15 & 14 & 13 & 12\\
\hline 11 & 10 & 9 & 8\\
\hline7 & 6 & 5 & 4\\
\hline3 & 2 & 1 & \\
\hline
\end{array}\]

A state machine model of the puzzle has states consisting of a $4\times 4$
matrix with 16 entries consisting of the integers $1,\dots,15$ as well as
one ``empty'' entry---like each of the two arrays above.

The state transitions correspond to exchanging the empty square and an
adjacent numbered tile.  For example, an empty at position $(2,2)$ can
exchange position with tile above it, namely, at position $(1,2)$:
\[\begin{array}{|c|c|c|c|}
\hline n_1 & n_2 & n_3 & n_4\\
\hline n_5 &  & n_6 & n_7\\
\hline n_8  & n_9 & n_{10} & n_{11}\\
\hline n_{12} & n_{13} & n_{14}  & n_{15}\\
\hline
\end{array} \longrightarrow
\begin{array}{|c|c|c|c|}
\hline n_1 &   & n_3 & n_4\\
\hline n_5 & n_2 & n_6 & n_7\\
\hline n_8  & n_9 & n_{10} & n_{11}\\
\hline n_{12} & n_{13} & n_{14}  & n_{15}\\
\hline
\end{array} 
\]

We will use the invariant method to prove that there is no way to reach
the target state starting from the initial state.

We begin by noting that a state can also be represented as a pair
consisting of two things:
\begin{enumerate}
\item a list of the numbers $1,\dots,15$ in the order in which they
appear---reading rows left-to-right from the top row down, ignoring the
empty square, and
\item the coordinates of the empty square---where the upper left
square has coordinates $(1,1)$, the lower right $(4,4)$.
\end{enumerate}

\bparts
\ppart Write out the ``list'' representation of the start state and the
``impossible'' state.

\solution{
start: ((1\ 2\ \dots\ 15), (4,4)),

impossible: ((15\ 14\ \dots\ 1), (4,4)), 
}
\eparts

Let $L$ be a list of the numbers $1,\dots,15$ in some order.  A pair of
integers is an \emph{out-of-order pair} in $L$ when the first element of
the pair both comes \emph{earlier} in the list and \emph{is larger}, than
the second element of the pair.  For example, the list $1,2,4,5,3$ has two
out-of-order pairs: (4,3) and (5,3).  The increasing list $1,2\dots n$ has
no out-of-order pairs.

Let a state, $S$, be a pair $(L, (i,j))$ described above.  We define the
\emph{parity} of $S$ to be the mod 2 sum of the number of out-of-order pairs in
$L$ and the row-number of the empty square (\emph{i.e.}, $(L + i) \bmod 2$).

\begin{problemparts}

\problempart Verify that the parity of the start state and the target
state are different.

\solution{The parity of the start state is
\[
(0+4) \bmod 2 = 0.
\]
The parity of target is 
\[
((15 \cdot 14/ 2) + 4) \bmod 2 = 1.
\]
}

\problempart Show that the parity of a state is invariant under transitions.
Conclude that ``the impossible'' is impossible to reach.

\solution{To show that the parity is constant, consider how moves may
affect the parity.  There are only 4 moves types of moves: a move to the
left, a move to the right, a move to the row above, or a move to the row
below.

Note that horizontal moves change nothing, and vertical moves both change
$i$ by 1, and move a tile three places forward or back in the list, $L$.
To consider how the parity is changed in this case, we need to consider
only the 3 pairs in $L$ that are between the tile's old and new position.
(The other pairs are not effected by the tile's move).  This reverses the
order of three pairs in $L$, changing the number of inversions by 3 or 1,
but always by an odd amount.

To confirm this last remark, note that if the 3 pairs were all out of
order or all in order before, the amount is changed by 3.  If two pairs
were out of order and 1 pair was in order or if one pair was out of order
and two were in order, this will change the amount by 1.  So the sum of
$i$ and the number of out-of-order pairs changes by an even amount (either
1+3 or 1+1), which implies that its parity remains the same.  Since the
initial state has parity 0 (even), all states reachable from the initial
state must have parity 0, so the target state with parity 1 can't be
reachable.}

\iffalse

\ppart (optional, extra credit) Show that if two states have the same
parity, then there is a way to get from one to the other.
\fi

\end{problemparts}

By the way, if two states have the same parity, then in fact there
\emph{is} a way to get from one to the other.  If you like puzzles, this
is a good one to think about on your own about after class.

\end{problem}
\newpage
\begin{problem}
The most straightforward way to compute the $b$th power of a number, $a$,
is to multiply $a$ by itself $b$ times.  This of course requires $b-1$
multiplications.  There is another way to do it using considerably fewer
multiplications.  This algorithm is called \emph{Fast Exponentiation}:

Given inputs $a \in \reals, b \in \naturals$,
initialize registers $x,y,z$ to $a,1,b$ respectively,
and repeat the following sequence of steps until termination:
\begin{itemize}
\item if $z=0$ \textbf{return} $y$ and terminate
\item $r := \text{remainder}(z,2)$
\item $z := \text{quotient}(z,2)$
\item if $r = 1$, then $y := xy$
\item $x := x^2$
\end{itemize}
We claim this algorithm always terminates and leaves $y = a^b$.

\bparts

\ppart  Model this algorithm with a state
machine, carefully defining the states and transitions.

\solution{\begin{enumerate}
\item $Q \eqdef\ \ \reals \cross \reals \cross \naturals$,
\item $Q_0 \eqdef\ \ \set{(a,1,b)}$,
\item transitions
\begin{equation*}
(x,y,z) \rightarrow
\begin{cases}
(x^2, y, \text{quotient}(z,2)) & \text{if $z$ is positive and even},\\
(x^2, xy, \text{quotient}(z,2)) & \text{if $z$ is positive and odd}.
\end{cases}
\end{equation*}
\end{enumerate}
}

\ppart Let $d \eqdef a^b$.  Verify that the following predicate, $P$, is
an invariant:
\[
P((x,y,z)) \eqdef\ \ [yx^z = d].
\]

\solution{See Week 5 Notes, \S5.3.}

\ppart Prove that the algorithm is partially correct: if it halts, it does
so with $y=d$.

\solution{See Week 5 Notes, \S5.3.}

\ppart Prove that the algorithm terminates.

\solution{See Week 5 Notes, \S5.3.}

\ppart In fact, prove that it requires at most $2 \log_2 b$
multiplications for the Fast Exponentiation algorithm to compute $a^b$ for
$b>1$.

\solution{The value of $z$ is initially $b$ and gets halved at least at
every other step.  So it can't be halved more than $\log_2 b$ times before
hitting zero.}

\eparts
\end{problem}


\iffalse

%Fast multiplication by adding and doubling from F97 pset4, problem 2.
%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

\begin{problem}
Consider the following multiplication algorithm, known as the ``Russian
peasant's multiplication'' to multiply numbers $a,b \in \naturals$.

The accumulator for the answer is register \texttt{p}; registers
\texttt{x}, \texttt{y} are for temporary storage.

\texttt{x:=}$a$; \texttt{y:=}$b$; \texttt{p:=}0;
\begin{verbatim}
Do until y=0:
 if even(y) then {x := 2x; y := y/2};
 if odd(y) then {p := p + x; x := 2x; y := (y-1)/2};
\end{verbatim}
We claim the product of $a$ and $b$ will be left in the accumulator
\texttt{p} when the procedure terminates.

Here is an example of the execution of the algorithm for $a=5, b = 9$:
\[\begin{array}{lccc}
\texttt{x}  &  \texttt{y} &   \texttt{p}\\
\hline
5 & 9 & 0\\
10 & 4 & 5\\
20 & 2 & 5\\
40 & 1 & 5\\
80 & 0 & 45
\end{array}\]

\begin{problemparts}

\problempart
Model the algorithm as a state machine.  

\solution{The state is the triple of values in \texttt{x, y}, and \texttt{p}.

There is just one start state: $(a,b,0)$.

There are two types of state transitions (even or odd) as described in the
algorithm:

If $y$ is even: $(x,y,p) \longrightarrow  (2x, y/2, p)$;

if $y$ is odd:  $(x,y,p) \longrightarrow (2x, (y-1)/2, p+x)$.
}

\problempart
Prove that it is correct using an invariant.

\solution{
To prove correctness, we show that
\begin{lemma*}
The predicate $P(x,y,p) \eqdef\quad [ab = xy+p]$ is an invariant.
\end{lemma*}

\begin{proof}
Consider a transition from $(x,y,p)$ to $(x',y',p')$ and suppose
$P(x,y,p)$ holds, that is, $ab = xy+p$.  We must prove that $P(x',y',p')$
holds, that is, $ab = xy+p$.  There are two cases based on the type of
action, \emph{even} or {\it odd}.

\emph{even}: Doubling $x$ while halving $y$ doesn't change the product
$xy$, and $p$ doesn't change.  So $x'y'+p' = xy+p = ab$.

\emph{odd}: $x' = 2x$, $y' = (y - 1)/ 2$, and $p' = p + x$.  So
\[
x'y' + p' = 2x(y - 1)/ 2 + p + x = (xy-x) + p + x = xy+p = ab.
\]
\end{proof}

Also, $P$ holds for the start state $(a,b,0)$ because $ab+0 = ab$.  So by
the Invariant Theorem, we conclude:
\begin{corollary*}
If $y=0$ in a reachable state, then $p = ab$.
\end{corollary*}

\begin{proof}
By our invariant, we have
$P(x,0,p)$, that is $x0 + p = ab$, so $x=ab$.
\end{proof}
}

\problempart
Why is this algorithm guaranteed to terminate?  How many arithmetic
operations $(+, -, \times, / )$
does it perform on given inputs $a$ and $b$?

\solution{Notice that the value of $y$ is a nonnegative integer that
decreases at every step unless it is 0: if $y$ is even, it becomes $y/2$
and if $y$ is odd, it becomes $(y-1)/2$.  So $y$ will eventually become 0,
and the algorithm must terminate.

In fact, since $y$ is a least halved each time around the loop, there are
at most $\floor{\log_2 b}+1$ loop executions, and each execution involves
1 multiply (by 2), one division (by 2), one addition, and at most one
subtraction.}

\end{problemparts}
\end{problem}
\fi

\iffalse

\begin{problem}
\textbf{extended gcd}
an important elementary fact from number theory is that
the gcd of two natural numbers can be expressed as an integer linear
combination of them.  in other words, 
\[
\forall m,n \in \naturals\, \exists k,l \in \integers\ \gcd(m,n) =  km+ln.
\]

in this problem you will verify that the euclidean alogorithm can be
extended to calculate the desired integer coefficients.  in particular,
given natural numbers $m,n$, with $n>0$, we claim the following
procedure\footnote{this procedure is taken from aho, hopcroft, and
ullman's text on algorithms.} halts with integers $k,l$ in registers
\texttt{k} and \texttt{l} such that
\[
km+ln = \gcd(m,n).
\]

inputs: $m,n \in \naturals, n>0$.

registers: \texttt{x,y,k,l,u,v,q}.

\begin{verbatim}
x := m; y := n; k := 0; l := 1; u := 1; v := 0; 
loop:
if y|x, then halt
else
  q := floor(x/y);      ;; same as q:= quotient of x divided by y
  {x := y,              ;; assignments within the braces are simultaneous
   y := x - q * y,      ;; same as y:= remainder of x divided by y
   u := k,
   v := l,
   k := u - q * k,
   l := v - q * l}      ;; assignments within the braces are simultaneous
goto loop
\end{verbatim}

note that \texttt{x,y} behave exactly as in the euclidean gcd algorithm
from lecture, except that this procedure stops one step sooner, ensuring
that $\gcd(m,n)$ is in \texttt{y} at the end.

\bparts

\ppart prove that this procedure terminates for all inputs $m,n$.

\solution{it terminates for the same reason as the euclidean algorithm:
the contents, $y$, of register \texttt{y} is a natural number-valued
variable that strictly decreases each time around the loop.}

\ppart we claim that invariant properties that can be used to prove partial
correctness are:
\begin{itemize}
\item %\label{gcd}
(a)  $\gcd(x,y) = \gcd(m,n)$,
\item % \label{kl}
(b) $km+ ln = y$, and
\item % \label{uv}
(c) $um+vn = x$.
\end{itemize}

prove that (a), (b) and (c) are ``loop'' invariants, that is, if they are
true at the start of the loop, they are true at the start of the next
loop.

\solution{invariant (a) is the same one as for the euclidean algorithm, which
we proved in lecture.  to check the other two invariants, note that at the
start $x=m, y=n, k=0, l=1$ so $km+ln=0m+1n=n=y$ as required; also $u=1, v=0$
and $um+vn= 1m+0n=m =x$ as required.

so let $x,y,k,l,u,v$ be the contents of registers \texttt{x,y,k,l,u,v} at
the start of the loop and assume that all the invariants hold for these
values.  we must prove that (b) and (c) hold (we already know (a) does)
for the new contents $x',y',k',l',u',v'$ of these registers at the next
time the loop is started.

now according to the procedure, $u'=k,v'=l,x'=y$, so invariant (c) holds
for $u',v',x'$ because of invariant (b) for $k,l,y$.  also, $k'= u - qk,
l'= v - ql, y' = x - qy$ where $q = \floor{x/y}$, so
\[k'm+l'n = (u-qk)m + (v-ql)n =um+vn - q(km+ln) = x - qy = y',\]
and therefore invariant (b) holds for $k',l',y'$.
}

\ppart prove that at termination, \texttt{y} contains $\gcd(m,n)$
and \texttt{k} and \texttt{l} contains integers $k$ and $l$ such that
\[
\gcd(m,n) = km+ln.
\]

\solution{it's easy to check that all three invariant are true at the
start of the first time around the loop.  so they are true at termination.
at termination the contents, $y$, of register \texttt{y} divides the
contents, $x$, of register \texttt{x}, so invariants (a) and (b) imply
\[
\gcd(m,n) = \gcd(x,y) = y = km + ln.
\]
so we have the gcd in register \texttt{y} and the desired coefficients in
\texttt{k}, \texttt{l}.}

\eparts
\end{problem}
\fi

\iffalse

%------------------------------------------------
% source: pset4 problem2 spring98: part a is from ps4 in spring'97
% topic: buckets
% last used:

\begin{problem}You are given two buckets, $A$ and $B$, a water hose, a
receptacle, and a drain.  The buckets and receptacle are initially
empty.  The buckets are labeled with their respectively capacities,
positive integers $a$ and $b$.  The receptacle can be used to store an
unlimited amount of water, but has no measurement markings.  Excess
water can be dumped into the drain.  Among the possible moves are:
\begin{enumerate}
\item\label{hose-bucket} fill a bucket from the hose,
\item pour from the receptacle to a bucket until the bucket is full
or the receptacle is empty, whichever happens first,
\item empty a bucket to the drain,
\item\label{bucket-receptacle} empty a bucket to the receptacle,
\item pour from $A$ to $B$ until either $A$ is empty or $B$ is full,
whichever happens first,
\item pour from $B$ to $A$ until either $B$ is empty or $A$ is full,
whichever happens first.
\end{enumerate}

\bparts 
\ppart
Model this scenario with a state machine.  (What are the states?  How does
a state change in response to a move?)

\solution{
The states are triples $(x,y,z)$ which give the current amount of
water in the bucket $A$, bucket $B$, and the receptacle, respectively.
The initial state is $(0,0,0)$.

The moves make the following transitions:
\begin{enumerate}
\item fill a bucket from the hose
$$
(x,y,z) \rightarrow \left \{ \begin{array}{l}
(a,y,z) \mbox{ if filling A from the hose } \\
(x,b,z) \mbox{ if filling B from the hose }
\end{array} \right.
$$

\item pour from the receptacle to a bucket until the bucket is full
or the receptacle is empty, whichever happens first
$$ 
(x,y,z) \rightarrow \left \{ \begin{array}{l} 
(a,y,z-(a-x)) \mbox{ if pouring to A and } z \geq (a-x) \\
(x+z,y,0) \mbox{ if pouring to A and } z < (a-x) \\
(x,b,z-(b-y)) \mbox{ if pouring to B and } z \geq (b-y) \\
(x,y+z,0) \mbox{ if pouring to B and } z < (b-y) 
\end{array} \right.
$$

\item empty a bucket to the drain
$$
(x,y,z) \rightarrow \left \{ \begin{array}{l}
(0,y,z) \mbox{ if emptying A to the drain } \\
(x,0,z) \mbox{ if emptying B to the drain }
\end{array} \right.
$$

\item empty a bucket to the receptacle
$$
(x,y,z) \rightarrow \left \{ \begin{array}{l}
(0,y,z+x) \mbox{ if emptying A to the receptacle } \\
(x,0,z+y) \mbox{ if emptying B to the receptacle }
\end{array} \right.
$$

\item pour from $A$ to $B$ until either $A$ is empty or $B$ is full,
whichever happens first
$$ 
(x,y,z) \rightarrow \left \{ \begin{array}{l} 
(0,y+x,z) \mbox{ if } x < (b-y) \\
(x-(b-y),b,z) \mbox{ if } x \geq (b-y)
\end{array} \right.
$$

\item pour from $B$ to $A$ until either $B$ is empty or $A$ is full,
whichever happens first
$$ 
(x,y,z) \rightarrow \left \{ \begin{array}{l} 
(x+y,0,z) \mbox{ if } y < (a-x) \\
(a,y-(a-x),z) \mbox{ if } y \geq (a-x)
\end{array} \right.
$$
\end{enumerate}
}

\ppart
\label{gcd-iff}

Prove that we can put $k\in\naturals$ gallons of water into the
receptacle using the above operations if and only if $\gcd(a,b) \mid k $.
\hint Use the fact that if $a,b$ are positive integers then there
exist integers $s,t$ such that $\gcd(a,b)=sa+tb$.

\solution{
We need to prove two facts (the ``iff'' statement has two directions):
\begin{enumerate}
\item
If $\gcd(a,b) \mid k $ then we can put $k$ gallons of water into
the receptacle.

\begin{proof}

Since there exist integers $s,t$ s.t.  $\gcd(a,b)=sa+tb$, then
if $\gcd(a,b) \mid k $ then there exists an integer $n$ s.t. $n
* \gcd(a,b) = k$, and hence $n(sa+tb)=k$.  Assume without loss
of generality that $sa\geq{tb}$ (otherwise exchange the buckets in the
following argument).  Then we can fill the receptacle with $k$ gallons: \\
First, we repeat $ns$ times moves $1$ and $4$, filling the $A$ bucket
and pouring its content into the receptacle (note that if $sa\geq{tb}$
then $s\geq{0}$).  With this series of moves we will get from state
$(0,0,0)$ to $(0,0,nsa)$.  Then, if $t=0$, we are already done since
$k=nsa$.  If $t>0$, we repeat $nt$ times moves $1$ and $4$ but now
using the bucket $B$.  This gets us from $(0,0,nsa)$ to
$(0,0,nsa+ntb)=(0,0,k)$.  If $t<0$ we repeat $n*(-t)$ times moves $2$
and $3$ using the bucket $B$.  At the end of this series we will be in
state $(0,0,nsa-n*(-t)b)=(0,0,nsa+ntb)=(0,0,k)$
\end{proof}

\item
If we can put $k$ gallons of water into the receptacle then
$\gcd(a,b) \mid k $.

\begin{proof}
We show that it is an invariant of our state machine that
$\gcd(a,b)$ divides $x$, $y$ and $z$.  It will prove in
particular, that $z$ is always a multiple of $\gcd(a,b)$

Let's denote $\gcd(a,b)$ by $c$.  The invariant is true in the
initial state $(0,0,0)$.\footnote{Remember that $(x\mid
y)\iff(\exists_{b\in\integers}\,\,\,y=xb)$}.  Each move preserves this
invariant, because in each move the new values of $x,y$ or $z$ are
always integer linear combinations of the previous values $x,y,z$ or
$a,b$, i.e., they are expressed by a formula
$n_1x+n_2y+n_3z+n_4a+n_5b$ for some
$(n_1,n_2,n_3,n_4,n_5)\in\integers^5$.  For example in move 2, case 1,
the new value of $z$ is expressed by the above formula with
$(n_1,n_2,n_3,n_4,n_5)=(1,0,1,-1,0)$.  Since $c$ divides $a$ and $b$,
if $c$ divides $x,y,z$ before the move, then it divides every such
linear formula, and hence it divides the values of $x,y$ and $z$ after
each move.
\end{proof}
\end{enumerate}
}

% \ppart Let's restrict the valid moves to numbers~\ref{hose-bucket}
% and~\ref{bucket-receptacle} only.  Prove that there exists a number
% $n$, such that for all integer $k\geq n$, we can fill the receptacle
% with $k$ gallons of water iff $\gcd(a,b) \mid k$.

% \solution{
% Again, pick $s,t$ s.t. $c=\gcd(a,b)=sa+bt$.  If both
% $s,t\geq{0}$ then $(s,t)=(0,1)$ or $(1,0)$, i.e., $a=b$ (check that in
% all other cases $c$ would be greater than either $a$ or $b$, which is
% impossible).  If $a=b$ then $c=a=b$, and for each $k\geq{c}$, $c\mid
% k$, we can fill the receptacle by repeating moves $1$ and $4$
% ${k}/{c}\in\naturals$ times (with any bucket, since $a=b$).

% Clearly it cannot be that both $s,t\leq0$ (or $c$ would be a
% non-positive integer).  So we are left with two cases: $t<0<s$ or
% $s<0<t$.  Assume without loss of generality that $t<0<s$.

% We show that if $k\geq{n}$ for $n=-t{b^2}/{c}$, and $k$ is a
% multiple of $c$, then we can fill the receptacle with $k$ gallons.
% Let's denote $k$ as a multiple of $b$ plus a ``remainder'' in the
% following way:
% %
% $$ k=k_1b+k_2c\mbox{, where
% }k_1,k_2\in\naturals\,\,\wedge\,\,0\leq{k_2}<\frac{b}{c} $$
% %
% We can represent $k$ in this way since it is divisible by $c$.  Notice
% also, that since $k\geq{-t{b^2}/{c}}$, then
% $k_1\geq{-t{b}/{c}}$.  Since $c=sa+bt$, we can rewrite $k$ as
% follows:
% \begin{eqnarray*}
% k&=&k_1b+k_2c
% \\
% &=&k_1b+k_2(sa+bt)
% \\
% &=&(k_2s)a+(k_1+k_2t)b
% \end{eqnarray*}
% Hence, as long as $k_1\geq{-t{b}/{c}}$, both $(k_2s)$ and $(k_1+k_2t)$
% are non-negative integers.  And hence, we can fill the receptacle by
% $(k_2s)$ times pouring bucket $A$ into it, and then $(k_1+k_2t)$ times
% bucket $B$, both just with moves $1$ and $4$.
% }

\eparts
\end{problem}
\fi

\end{document}
