\documentstyle[12pt,amstex,twoside]{article}
\input{macros-course}

\begin{document}
\pset{5}{March 4, 1997}{March 11, 1997}

{\bf Reading:} State machine handout.

Remember that correctness involves termination plus the right answer!

\begin{problems}


\problem Read the description of the RSA cryptosystem from the textbook, 
pp 146-148. 
\begin{problemparts}
\problempart
Given primes $p = 173$ and $q=149$ generate encryption and
decryption keys, $e$ and $d$ respectively, such that $e\cdot d = 1$
mod $ (p-1)(q-1)$.  For ``security,'' make $e,d \ge 20$.
\problempart
Convert the word ``MIT'' to a number by first mapping each letter to
its position in the alphabet, e.g. A $= 0$, B $= 1$, C $= 2$, $\ldots$,
Z $= 25$, and then gathering the numbers $(M,I,T)$ into a single
number $26^2*M+26*I+T$.  Find the RSA-encrypted version of ``MIT'' and
show that it decrypts properly.
\problempart What happens when you apply the encrypt/decrypt
operation to ``YOU''?  Why?
\end{problemparts}

\problem
Consider the following algorithm PolyEval, which takes a list of
arguments $a_0,\ldots,a_n$ and an argument $x$, and is supposed to
compute the value of the polynomial
\[
\sum_{i=0}^n a_i x^i.
\]
Prove that the algorithm is correct.

\begin{tabbing}
else \= else \= else \= else \= \kill
PolyEval$(a_0,\ldots,a_n,x)$\\
\\
\>   $s=0$\\
\>   for $i=n$ downto $0$\\
\>   \>    $s=x*s+a_i$\\
\>   return $s$
\end{tabbing}

\problem 

Write a (pseudocode) program that when given a natural number $n$ 
returns the binary representation of $n$.
(the output of the program must be a string over the
alphabet $\{0,1\}$).    Use standard primitive
operations.
Prove that your program is correct.


Procedure Bin(d)

$c := d$ \\
$i := 0$ \\
while ($c/2 > 0$) \{ 

\hspace{.5in} $b[i] := c \mbox{ mod } 2$

\hspace{.5in} $c := c/2$

\hspace{.5in} $i := i+1$

\} \\
$b[i] = a$ \\

The above while loop terminates because any number $d$ can be divided by $2$ 
and give nonzero results at most $\lfloor \log_2(d) \rfloor$ times.  
Now we prove that the program is correct.

Let $d$ have the representation $d = \sum_{i=0}^{\infty}{a_i 2^{i}}$.
Note that $d/2^{k} = \sum_{i=k}^{\infty}{a_i 2^{i-k}}$.

\begin{theorem}
When $i=k$ we have the following invariants

$b[k] = a_{k}$ 

$c = d/2^{k+1}$

\end{theorem}

\begin{proof}

BASE CASE: When $i=0$, $b[0] = d \mbox{ mod } 2 =a_0$, and
$c = d/2 = d/2^1$.\\

INDUCTIVE STEP: Suppose $i=k+1$.  Then by the inductive hypothesis,
$c = d/2^{k+1}$, so we have $b[k+1] := d/2^{k+1} \mbox{mod } 2 = a_{k+1}$
and $c := c/2 = d/(2^{k+1} \cdot 2) = d/2^{k+2}$.

So the algorithm terminates in  $\lfloor \log_2(d) \rfloor + 1$ steps with
the $i$th order bit in $b[i]$. 

\end{proof}

\problem Consider the following algorithm to find the greatest common
divisor of a collection of numbers $a_1,\ldots,a_n$.  It uses
algorithm Euclid for finding the GCD of two numbers.  Prove it is
correct (you might want to prove a lemma about
GCD$(a,$GCD$(b_1,\ldots,b_k))$).

\begin{tabbing}
else \= else \= else \= else \= \kill
MultiEuclid$(a_1,\ldots,a_n)$\\
\\
\>  $r=a_1$\\
\>  for $i=2$ to $n$\\
\>     \> $r=$Euclid$(r,a_i)$\\
\>  return $r$
\end{tabbing}

\problem 

The following code estimates the value of \( \frac{1}{1-x/2} \) to
within an additive error of $1/1024$ for $0< x < 1 $.  Prove that it
is correct.

\begin{verbatim}
estimate(x) 
{ 
  Fprev = 0;
  Fnext = 1;
  while (Fnext - Fprev > 1/1024) {
    Fprev = Fnext;
    Fnext = (Fprev * x / 2) +1;
  }
  return(Fnext);
}
\end{verbatim}

\begin{theorem}
In the $n$th step of the algorithm we have: \\
Fprev $= \sum_{i=0}^{n-1}{(\frac{x}{2})^i} $ \\
Fnext $= \sum_{i=0}^{n}(\frac{x}{2})^i $ \\
\end{theorem}

\begin{proof}
BASE CASE: In the $0$th step Fprev $=0= \sum_{i=0}^{-1}{(\frac{x}{2})^i} $,
Fnext $=1= \sum_{i=0}^{0}{(\frac{x}{2})^i}$. \\

INDUCTIVE STEP: At the $(n+1)$th step we have:

Fprev := Fnext =  $= \sum_{i=0}^{n}{(\frac{x}{2})^i} $

Fnext := (Fprev$*x/2)+1 = x \sum_{i=0}^{n}{(\frac{x}{2})^i}/2 +1 =
\sum_{i=0}^{n+1}{(\frac{x}{2})^i}$.

\end{proof}

From the above theorem, termination follows trivialy because
Fnext - Fprev $=(\frac{x}{2})^n$ becomes less than 1/1024 for sufficiently
high $n$.  

To see that the algorithm computes $\frac{1}{1-x/2}$ within an error of
1/1024, note that 

\begin{math}
\frac{1}{1-x/2} = \sum_{i=0}^{\infty}{(\frac{x}{2})^i} =
\sum_{i=0}^{n}{(\frac{x}{2})^i} + \frac{1-(x/2)^{n+1}}{1-x/2}
\end{math} 

But, $\frac{1-(x/2)^{n+1}}{1-x/2}$ = $\frac{(x/2)^n}{2/x-1} < (x/2)^n$.

\problem   The mode of a list is an element appearing as frequently in
the list as any other.  Let $A[i..j]$ denote the sublist of $A$
with indices between $i$ and $j$, inclusive.
Consider the following algorithm.

\begin{tabbing}

Mode($A$) \\
\ \ \ \= if (size[A] = 1) \\
      \> \ \ \ \= return(A[1]) \\
      \> if ($A[1] = \mbox{Mode}(A[2..size[A]])$) \\
      \>       \> return(A[1]) \\
      \> else\\
      \>       \>return(Mode($A[2..(size[A])]$)) \\
\end{tabbing}

What is the fallacy in the following argument that Mode returns the
mode of $A$?  Explain the fallacy, and give a counterexample showing
the algorithm fails.  

Proof by induction on the length of the input.  The base case is
trivial.  So assume the hypothesis true for inputs of length $n$.
Consider an input of length $n+1$.  Then by induction, each of the two
recursive calls properly returns the mode of its argument.  Thus, if
$A[1]$ is the mode, the if test succeeds, and the function returns the
correct value.  If $A[1]$ is not the mode, then clearly removing
$A[1]$ doesn't change the mode, so the second recursive call succeeds
and returns the correct value.

\bigskip

Counterexample: \{2,2,3 \} (the program returns 3).

The fallacy in the proof is the implicit assumption that the mode of a list
is unique.  When a sublist of two distinct elements is passed in the program, 
it arbitrarily returns one of them, and this may not end up being a mode of
the whole list.
 

\problem

A {\em  search tree} is either:
\begin{itemize}
\item An {\em empty tree} with no nodes
\item A {\em root node} with {\em key} $k$, and
\begin{itemize}
\item a {\em left subtree,} all of whose nodes have keys less than $k$
\item a {\em right subtree,} all of whose nodes have keys exceeding $k$.
\end{itemize}
\end{itemize}

The following fallacious algorithm Find, when called with key $k$ and
$(a,b)$ search tree $T$, should print ``found it'' if and only if $k$ is the
key of a node in the search tree.

\begin{tabbing}
else \= else \= else \= else \= \kill
Find$(k,T)$\\
\\
\>   $c=$key$($root-node$(T))$\\
\>   if $(k=c)$\\
\>   \>   print ``found it''\\
\>   else if $(k<c)$\\
\>   \>   Find$(k,$left-subtree$(T))$\\
\>   else \\
\>   \>   Find$(k,$right-subtree$(T))$\\
\>
\end{tabbing}

\begin{problemparts}
\problempart (3 points)
What is wrong with the above algorithm?  Add a starting if-test that
will fix the problem.
\problempart (7 points)
Prove that your (fixed) algorithm does what it should.
\end{problemparts}

\bigskip

Fixed algorithm: \\

\begin{tabbing}
else \= else \= else \= else \= \kill
Find$(k,T)$\\
\\
\>   if (empty) print ``Key not in the tree''\\
\>   $c=$key$($root-node$(T))$\\
\>   if $(k=c)$\\
\>   \>   print ``found it''\\
\>   else if $(k<c)$\\
\>   \>   Find$(k,$left-subtree$(T))$\\
\>   else \\
\>   \>   Find$(k,$right-subtree$(T))$\\
\>
\end{tabbing}

\begin{theorem}
For a tree of length $n$, the algorithm terminates in at most $n$ steps.
Furthermore, if the key is in the tree it prints the message ``found it'',
otherwise it prints the message ``Key not in the tree''.
\end{theorem}

\begin{proof}

BASE CASE: If the tree is empty the algorithm terminates in $0$ steps with the 
message ``Key not in the tree''. \\

INDUCTIVE STEP:  Given a tree of length $n+1$, the algorithm checks if the key 
is in the root. If it is, it prints ``found it'', and terminates in 1 step.
Otherwise, it calls the algorithm for a subtree of length $n$ and,
by  the inductive hypothesis, the algorithm terminates in at most $1+n$ steps.
Furthermore, if the key is in the tree, the algorithm looks at the correct 
subtree because if $k<c$, it calls Find on the left subtree which by definition
contains keys less than c, while if $k>c$, it calls Find on the right subtree
which contains keys greater than c. 

\end{proof}


\newcommand{\ef}[2]{
\begin{tabbing}       
XX\= XX\=XX\=XX\=XX\=XX\=   \kill
\protect #1\\
\>Effect: \+ \+ \\ 
   #2  \- \-
\end{tabbing}}

\newcommand{\iocode}[2]{\begin{center}\footnotesize
\begin{minipage}[t]{.45\linewidth}
\hbox to\linewidth{}
#1
\end{minipage}
\hspace{.05\linewidth} 
\begin{minipage}[t]{.45\linewidth}
\hbox to\linewidth{}
#2
\end{minipage}
\end{center}}

\newcommand{\prcef}[3]{\begin{tabbing}       
XX\=  XX\=XX\=XX\=XX\=  \kill
\protect #1\\
\>Precondition: \+ \+ \\ 
  #2  \-  \- \\ 
\>Effect: \+  \+ \\
  #3 \- \- 
\end{tabbing}} 

\problem

Consider a coin exchanger described by the 
following state machine.

The state set $Q$ consists of values for state components:
\begin{tabbing}
XXX\=XXX\= \kill
\> $\ms{total} \in I\!\! N$ \\
\> $\ms{total'} \in I\!\! N$ \\
\> $\ms{cents} \in I\!\! N$ \\
\> $\ms{dimes} \in I\!\! N$ \\
\> $\ms{quarters} \in I\!\! N.$ \\
\end{tabbing}

Here $\ms{total}$ is an initial amount of money (in cents) given 
as input to the machine.
All other variables are initially set to $0$.
When the machine terminates (no more transitions are possible)
the variables $\ms{cents}, \ms{dimes}$ and $\ms{quarters}$
should be the correct change corresponding 
to the input $\ms{total}$.
$\ms{total'}$ is an auxiliary variable.

The transition function $\delta$ is defined by the 
following rules.


\iocode{

\prcef{$\ms{give-quarter}$}
{% Precondition: \\
   $\ms{total}-\ms{total'} \geq 25$}
{% Effect: \\
   $\ms{total'} := \ms{total'} + 25$ \\
   $\ms{quarters} := \ms{quarters} + 1$}

\prcef{$\ms{give-dime}$}
{% Precondition: \\
   $25 > \ms{total}-\ms{total'} \geq 10$}
{% Effect: \\
   $\ms{total'} := \ms{total'} + 10$ \\
   $\ms{dimes} := \ms{dimes} + 1$}

}{

\prcef{$\ms{give-cent}$}
{% Precondition: \\
   $10 > \ms{total}-\ms{total'} > 0$}
{% Effect: \\
   $\ms{total'} := \ms{total'} + 1$ \\
   $\ms{cents} := \ms{cents} + 1$}
}

Prove using the invariant method that the algorithm is correct,
that is, when the machine terminates the total amount of 
money described by the variables
$\ms{cents}, \ms{dimes}, \ms{quarters}$
is exactly $\ms{total}$.

\problem (optional)

Consider the following procedure Bump, which operates on an infinite
array of bits $b[0],b[1],b[2],\ldots$ that are all initially 0.
\begin{tabbing}
else \= else \= else \= else \= \kill
Bump$(k)$\\
\\
\>  if $b[k]=0$ then\\
\>     \> $b[k]=1$\\
\>  else\\
\>     \> $b[k]=0$\\
\>     \> Bump$(k+1)$\\
\>  end if\\
\end{tabbing}

What will the $b[i]$ contain if Bump$(0)$ is called $n$ times?  Prove it.

\end{problems}
\end{document}

% Local Variables: 
% mode: latex
% TeX-master: t
% End: