\documentstyle{article}
\begin{document}

\large{

\begin{center}
CSCI220 \\
Spring 1992 Midterm Exam \\
February 14, 1992
\end{center}

This is an open book exam.
The total maximum attainable score for this exam is 100.  The score for each
question is given so that you can budget your time.
Partial credit may be given.
You will be graded on clarity and
conciseness as well as correctness.
Good luck!
\vspace{0.2in}

Problem 1 [50 points].  Prove that the following algorithm is correct, i.e., if
{\em Pre} is satisfied before the algorithm runs, then {\em Post} is satisfied
after termination of the algorithm.
\begin{verbatim}
(*Pre: n >= 1*)
readln(n);
i := 2;
fact := 1;
while i <= n do begin
   fact := fact*1;
   i := i+1
   end;
writeln(fact)
(*Post: fact = n!. n! is defined as the product of the integers 1,2,...,n*)
\end{verbatim}
Follow this outline:
\begin{enumerate}
\item  Use this loop invariant ($S(j)$):  If we reach the {\em while} test
$i \leq n$ and i has value j, then the value of the variable fact is $(j-1)!$

\item  Prove the loop invariant by induction on $j$.  Remember to use {\em
Pre}.

\item  What holds when the test at the beginning of the {\em while} loop
fails?

\item  Prove that {\em Post} follows from what you showed in $(3)$.
\end{enumerate}

Problem 2 [25 points].  Do exercise 2.16 in the textbook (p.35), but let the
input size be $n = 2^{6} = 64$ and 
use only
$T(n) = k_{6} \lg_{2} n$.
Also, briefly compare in English your result with the results of cases (a) and
(e), which you did as part of your homework and were discussed in class.

Problem 3 [25 points].  Consider exercise 3.6 in the textbook (p.57).
Let $n = 4$, where $n$ is the size of array $A$, for this problem.  \\
A suitable potential
function for the amortized complexity of {\em Increment} is the number of
``one'' bits in array $A$.
For example, \\
$\Phi(0000) = 0$, $\Phi(0111) = 3$, $\Phi(1000) = 1$, $\Phi(1011) = 3$,
$\Phi(1111) = 4$.
Assume that the characteristic operation for this problem is updating an entry
in $A$ (i.e., assigning zero or one to it).  Fill in the table below, which
is similar to Tables 3.2 and 3.3 in the textbook.  Note that you are asked {\em
only} to fill in the table, {\em not} to use it to solve exercise 3.6.
} %end of large
\begin{center}
\begin{tabular}{cccccc}
 $i$ & Operation & $S$ & $\Phi(S)$ & $t_{i}$ & $a_{i}$ \\
 \hline
  &           & 0000 & 0 &   &   \\
1  & {\em Increment} & 0001 & 1 & 1 & 2 \\
2  & {\em Increment} & 0010 & 1 & 2 & 2 \\
3  & {\em Increment} &      &   &   &   \\
4  & {\em Increment} &      &   &   &   \\
5  & {\em Increment} &      &   &   &   \\
6  & {\em Increment} &      &   &   &   \\
7  & {\em Increment} &      &   &   &   \\
8  & {\em Increment} &      &   &   &   \\
9  & {\em Increment} &      &   &   &   \\
10 & {\em Increment} &      &   &   &   \\
11 & {\em Increment} &      &   &   &   \\
12 & {\em Increment} &      &   &   &   \\
13 & {\em Increment} &      &   &   &   \\
14 & {\em Increment} &      &   &   &   \\
15 & {\em Increment} &      &   &   &   \\
\end{tabular}
\end{center}
\end{document}