\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}

\section*{Midterm \hfill{\parbox{3in}
    {\small\sc\begin{flushright} October 14, 1993. 5:00--6:15
PM\end{flushright}}}}

There are four problems for a total of 100 points.
Show all your work, partial credit will be awarded.
When there is not enough room on the test page itself,
write in the provided blue books and write and sign your name
on each one. No notes, no collaboration.
\begin{center}
If a problem seems easy: take care!\\
If a problem seems hard: persevere!
\end{center}
~\\[.25in]
{\Large Name: \hrulefill}
\\[.5in]

\center{
{\Large
\begin{tabular}{c|c}
Problem & Credit \\ \hline\hline
 1 & \\ \hline 2 & \\ \hline 3 & \\ \hline 4 & \\ \hline\hline
  Total & \end{tabular} }}
   


\newpage
\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}
\newpage

\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}
\newpage

\item Given two lists, $L_1$ and $L_2$, the operation of
concatenation is defined as third list with all the elements
of $L_1$, in order, followed by all the elements of $L_2$, in order.
For example, if the two lists are:
\[
  L_1 = a \rightarrow b \rightarrow c, \mbox{~~~~}
   L_2 = d \rightarrow e \rightarrow f 
\]
then the concatenation would be,
\[ \mbox{\verb.Concat.}(L_1, L_2) = 
 a \rightarrow b \rightarrow c \rightarrow d \rightarrow e \rightarrow f \]
A list is given by the following code fragment:
\begin{verbatim}
{    A list is a pointer to a header record       }
{    which contain pointers to the first and last }
{    elements in the list.                        }
type List = ^ListHeader ; 
     ListElement = ^ListRecord ; 
     ListHeader = record
         first : ListElement ;
         last  : ListElement ; 
         end ;
     ListRecord = record    
         data : DataType ;
         next : ListElement
         end ;
{    An empty list is a listHeader                }
{    with first = last = nil .                    }
\end{verbatim}
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.
\newpage

\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\,)$ multiplications 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}

\end{enumerate}
\end{document}

