\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*{Final \hfill{\parbox{3in}
    {\small\sc\begin{flushright} December 14, 1993. 5:00--7:30
PM\end{flushright}}}}

There are six problems each counting equally.
Show all your work, partial credit will be awarded.
~\\[.25in]
{\Large Name: \hrulefill}
\\[.5in]

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

\vfill
\parbox{3.5in}{
\em On my honor, I have neither given nor received
aid on this examination-assignment.\\
~\\
Signature: \hrulefill
}


\newpage
\begin{enumerate}
\item Show that these two program fragments are identical.
The variables \verb.A., \verb.B. and \verb.C. are declared as
\verb.boolean., and \verb.S1. represents a statement.
\begin{verbatim}
Program Fragment 1:

  if A then 
  begin
     if B then S1
     else if C then S1
  end ;

Program Fragment 2:

  if ((A AND B) OR (A AND C)) then S1 ;

\end{verbatim}
\newpage

\item
Change the following \verb.while. loop into 
an exactly equivalent program
which uses {\em only} recursion.
That is, define a procedure or function which
{\em does not} use any \verb.while. or \verb.repeat.
loops (nor any goto's), but which can call itself,
and replace the line labeled ``Replace Me'' with
a call to this function or procedure.

\begin{verbatim}
   a[N] := 0 ;
   i := 1 ;
   while a[i]>0 do i := i + 1 ;  {REPLACE ME}
   {Postcondition: i is minimum >= 1
                   such that a[i]<=0. }
\end{verbatim}
\newpage

\item 
Write a function that reverses the order of the elements
on a list. For instance, if the list \verb.L. looks like:
\[\begin{picture}(230,40)(0,0)
\put(0,0){\framebox(20,20){}}
\put(10,10){\circle*{3}}
\put(50,0){\framebox(20,20){A}}
\put(70,0){\framebox(20,20){}}
\put(80,10){\circle*{3}}
\put(120,0){\framebox(20,20){B}}
\put(140,0){\framebox(20,20){}}
\put(150,10){\circle*{3}}
\put(210,0){\line(1,1){20}}
\put(190,0){\framebox(20,20){C}}
\put(210,0){\framebox(20,20){}}
\put(10,10){\vector(1,0){40}}
\put(80,10){\vector(1,0){40}}
\put(150,10){\vector(1,0){40}}
\end{picture}\]
then \verb.Rev(L). should look like:
\[\begin{picture}(230,40)(0,0)
\put(10,10){\vector(1,0){40}}
\put(80,10){\vector(1,0){40}}
\put(150,10){\vector(1,0){40}}
\put(0,0){\framebox(20,20){}}
\put(10,10){\circle*{3}}
\put(50,0){\framebox(20,20){C}}
\put(70,0){\framebox(20,20){}}
\put(80,10){\circle*{3}}
\put(120,0){\framebox(20,20){B}}
\put(140,0){\framebox(20,20){}}
\put(150,10){\circle*{3}}
\put(210,0){\line(1,1){20}}
\put(190,0){\framebox(20,20){A}}
\put(210,0){\framebox(20,20){}}
\end{picture}\]
Take as a list definition:
\begin{verbatim}
Type 
    ListPntr = ^ ListRec ;
    ListRec = record 
        d : dataType ;
        n : ListPntr ;
        end ;
    List = ListPntr ;
\end{verbatim}
{\sc Hint:} You can do it in a single front to back
pass over the list, without the need
for \verb.new. or \verb.dispose..
Or you might try recursion, but this is not really simpler.
\newpage

\item Rotate the following tree at \verb.X.. That is, make
node \verb.X. the root via a single rotation.
\[\begin{picture}(130,90)(-50,-60)
\put(0,0){\line(-2,-1){40}}
\put(0,0){\line(2,-1){40}}
\put(-40,-20){\line(1,-1){20}}
\put(40,-20){\line(1,-1){40}}
\put(40,-20){\line(-1,-1){40}}
\put(60,-40){\line(-1,-1){20}}
\put(0,0){\circle*{5}}
\put(-40,-20){\circle*{5}}
\put(40,-20){\circle*{5}}
\put(-20,-40){\circle*{5}}
\put(20,-40){\circle*{5}}
\put(60,-40){\circle*{5}}
\put(0,-60){\circle*{5}}
\put(40,-60){\circle*{5}}
\put(80,-60){\circle*{5}}
\put(50,-20){X}
\end{picture}\]

\newpage

\item 
For this problem and the next, let 
\verb,X[1..N], be a global array of integers.

Consider the following procedure which exchanges the
largest element among \verb,X[a..b], with \verb.X[a]..
\begin{verbatim}
    procedure FindLarge(a,b:integer) ;
    var i,j, temp : integer ;
    begin
    {Prec: 1<=a<=b<=N }
       i := a ;
       j := i ;
    {Loop Inv: X[i] largest in X[a..j]}
       while j<=b do begin
          if X[j]>X[i] then i := j ;    { COUNT ME }
          j := j + 1 
       end ;
       temp := X[a] ;
       X[a] := X[i] ;
       X[i] := temp
    end ;
\end{verbatim}
Calling the procedure twice, we can find the {\em second
largest} in the array \verb,X[1..n],:
\begin{verbatim}
   function Slow : integer ;
   begin
      FindLarge(1,N) ;
      FindLarge(2,N) ;
      Slow := X[2] 
   end ;
\end{verbatim}
The line ``Count Me'' in \verb.FindLarge. is run:
\[ k_sN+d_s \]
times during the execution of \verb.Slow., for some $k_s$ and $d_s$.
{\em Determine the exact value of $k_s$.}
\newpage

\item
This problem is a continuation of the previous problem.

The following program also determines the second largest
element in the array \verb,X[1..n],. 
The line ``Count Me'' in the procedure \verb.FindLarge. is
run $k_fN+d_f$ times, {\em total} for all three calls to
\verb.FindLarge., during the execution of \verb.Fast..
{\em Determine the exact value for $k_f$.}
\begin{verbatim}
   function Fast : integer ;
   var half : integer ;
   begin

   {Prec: N >= 2 }
   {Find the largest in each of the two halves of the array}
      half := (N div 2) + 1 ;
      FindLarge( 1, half-1 ) ;
      FindLarge( half, N ) ;

   {Find the second largest in only one half.}
      if X[1]>X[half] then
         FindLarge( 2, half-1 )
      else
         FindLarge( half+1, N ) ;

   {Choose the correct among the three.}
      if X[1] > X[half] then
         if X[2]>X[half] then
            Fast := X[2]
         else Fast := X[half]
      else if X[1] < X[half] then 
         if X[half+1]>X[1] then
            Fast := X[half+1]
         else Fast := X[1] 
      else { X[1]=X[half] }
         Fast := X[1]

   end ;
\end{verbatim}
\end{enumerate}
\end{document}

