\documentstyle[12pt]{article}

\pagestyle{myheadings}
\def\headlineaux{\sc Math 220/317: Programming II/Data
Structures\hrulefill}
\markboth{\headlineaux}{\headlineaux}


\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burton Rosenberg}}
\end{centerline}\end{titlepage}

\newcommand{\outdate}{19 October 1993}
\section*{Midterm Answers \hfill{\parbox{3in}
    {\small\sc\begin{flushright} Out: \outdate\end{flushright}}}}
  

\begin{enumerate}
\item Show that these two program fragments are identical.
The variables \verb.A. and \verb.B. are declared as
\verb.boolean., and \verb.S1. and \verb.S2. represent
two statements.
\begin{verbatim}
Program Fragment 1:

  if A OR B then 
    if A then S1
    else S2 ;

Program Fragment 2:

  if A then S1 
    else if B then S2 ;

\end{verbatim}

\noindent {\sc Solution:} 
Transform the first fragment to:
\begin{verbatim}
  if (A OR B) AND A then S1 ;
  if (A OR B) AND (NOT A) then S2;
\end{verbatim}
The absorption identity gives:
\[ ( A \lor B ) \land A = A,\]
which we can apply to the first \verb.if..
Note: $\lor$ is the symbol for \verb.OR., $\land$ is the symbol for \verb.AND.,
and $\neg$ is the symbol for \verb.NOT..
The law of distribution gives:
\[ ( A \lor B ) \land ( \neg A ) = ( A \land \neg A ) \lor ( B \land \neg A ).\]
The first term of the OR on the right hand side is always false, so it reduces to
only the second term. Therefore, we can transform our program again:
\begin{verbatim}
  if A then S1 ;
  if (B AND NOT A) then S2;
\end{verbatim}
which is the same as:
\begin{verbatim}
  if A then S1
    else if B then S2;
\end{verbatim}
which is Program Fragment Two.

\item
Change the following \verb.repeat. loop into an
exactly equivalent \verb.while. loop.

\begin{verbatim}
  {Precondition: N is any integer.}
  i := 0 ;
  repeat
    i := i + 1 
  until (i*i) > N ;
\end{verbatim}

\noindent
{\sc Solution:}
The formula is:
\[ \mbox{ repeat } {\cal S } \mbox{ until } {\cal C}\; \Leftrightarrow \;
      {\cal S }; \mbox{ while } \neg {\cal C } \mbox{ do } {\cal S }.\]
Applying the formula:
\begin{verbatim}
  i := 0 ;
  i := i + 1 ;
  while not( (i*i)>N ) do
    i := i + 1 ;
\end{verbatim}
We can neaten this up using simple identities:
\begin{verbatim}
  i := 1 ;
  while (i*i)<=N do
    i := i + 1 ;
\end{verbatim}

\item
Give code for the procedure
\begin{verbatim}
   Procedure Concat(A, B : List ) ;
\end{verbatim}
which given two lists \verb.A. and \verb.B., changes \verb.A.
into their concatenation and changes \verb.B. into the
empty list. Do this with as efficiently as possible.
\begin{verbatim}
Procedure Concat( a, b: list ) ;
begin 
  if b^.first=nil then begin
    {there is nothing to do in this case}
  end else if a^.first=nil then begin
    {b is not empty, a is empty.}
    {copy b to a}
    a^.first := b^.first ;
    a^.last := b^.last ;
    {and make b empty}
    b^.first := nil ;
    b^.last := nil 
  end else begin
    {both a and b are not empty}
    {connect the list together}
    a^.last^.next := b^.first ;
    {update list a}
    a^.last := b^.last ;
    {and make b empty}
    b^.first := nil ;
    b^.last := nil
  end 
end;
\end{verbatim}
But then we notice that the last three lines of the last
two cases are identical, so we can pull them out and put
them together:
\begin{verbatim}
Procedure Concat( a, b : List ) ;
begin
  if b^.first<>nil then begin
    if a^.first=nil then {a becomes b}
      a^.first := b^.first 
    else {tack on non-empty b to non-empty a}
      a^.first^.next := b^.first ;
    {update a and make b nil}
    a^.last := b^.last ;
    b^.first := nil ;
    b^.last := nil 
  end 
end ;
\end{verbatim}
   


\item Improve the speed in the inner loop of the following code
fragment.
\begin{enumerate}
\item As written, how many multiplications are performed as a
function of $N$.
\item Give an identically functioning code fragment where only
$O\,(\,N\,)$ multipilications are performed.
\end{enumerate}
\begin{verbatim}
  var a : array[1..N,1..N] of integer ;
      i, j : integer ;
  begin
    for i := 1 to N do
      for j := i to N do
        a[i,j] := i*i ;
  end.
\end{verbatim}

\noindent{\sc Solution:}
There are,
\[ N + (N-1) + \ldots + 1 = (N+1)N/2,\]
multiplcations performed.

It would be best to pull the multiplication out of the inner loop,
doing it one time for all just before the do loop:
\begin{verbatim}
  for i := 1 to N do begin
    k := i*i ;
    for j := i to N do
      a[i,j] := k 
  end ;
\end{verbatim}
  
\end{enumerate}
\end{document}

