\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 20, 1994. 
\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 booleans 
whose values are calculated elsewhere in the program.
\verb.S1. and \verb.S2. are two statements.
\begin{verbatim}
Program Fragment 1:

  if A then
    if B then S1 ;
  if (NOT( A OR B )) then S2 ;

Program Fragment 2:

  if (NOT A) then begin
    if (NOT B) then S2 
    else if A then S1 
  end ;
  if (B AND A) then S1 ;
\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
Write code to split a list into two lists by taking elements
alternately from the original list.
The original list ends up empty. That is, just move pointers,
you don't have to new or dispose.
Keep the order of the elements and assume no dummy headers.
\begin{verbatim}
     type L_ptr = ^ L_rec ;
          L_rec = record
                i : integer ;
                n : L_ptr ;
          end ;

     procedure split_list( var in_list : L_ptr ; 
            var out_list_A : L_ptr ;
            var out_list_B : L_ptr ) ;
     (* you write the code here *)
\end{verbatim}
Here is an example. The symbols such as \verb.[x]->[y]->[z]. mean
list element containing data \verb.x. pointing to list element
containing data \verb.y., and so on.
\begin{verbatim}
   Input list:  [1]->[7]->[6]->[3]->[9]->[2]
   Output list A:  [1]->[6]->[9]
   Output list B:  [7]->[3]->[2]
\end{verbatim}
Be careful, the input list can be any length, including zero!
\newpage

\item 
Use recursion to compare two lists for equality. Lists are equal
when the nodes contain the same data, in the same order.
The data types are \verb.L_ptr. and \verb.L_rec., as in the
previous problem. The function header is:
\begin{verbatim}
function list_compare( a : L_ptr ; b : L_ptr ) : boolean ;
(* true if a equals b, and false otherwise.
   Recursion equation to employ:
   a=b if and only if either 
      (1) they are both empty
      (2) they are both non-empty, a^.i = b^.i 
          and the lists a^.n and b^.n are equal.
*)
   (* you write the code here *)
\end{verbatim}

\end{enumerate}
\end{document}

