\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 8, 1994.
\end{flushright}}}}

There are three problems for a total of 99 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.
~\\[.25in]
{\Large Name: \hrulefill}
\\[.5in]

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

\newpage
\begin{enumerate}
\item
Finish writing the following Quicksort program:
\begin{verbatim}
type MyArray = array [0..1000] of integer ;

procedure QuickSort( var A : MyArray ; i,j : integer ) ;
var M: integer ; (* index of split *)
    i_, j_: integer ; (* helper indices *)
    s : integer ; (* splitter value *)
begin
   if i<j then begin
      (* Split A[i..j], setting M such that:
         1) i <= M <= j
         2) A[k] <= A[M], for all i <= k < M
         3) A[M] <= A[k], for all M < k <= j
       *)











      (* recurse *)
      QuickSort( A, i, M-1 ) ;
      QuickSort( A, M+1, j ) ;
   end  (* if statment *)
end ; (* procedure QuickSort *)
\end{verbatim}
\newpage

\item
Finish writing the following tree insert program:
\begin{verbatim}
type tree = ^tree_rec
     tree_rec = record
                left, right : tree ;
                data : integer ;
                end ;

procedure tree_insert( var t : Tree ; v : integer ) ;
begin
   if (t<>NIL) then begin












   end (* if *) else begin
      new(t) ;
      t^.left := NIL ;
      t^.right := NIL ;
      t^.data := v ;
   end (* else *)
end ; (* procedure tree_insert *)
\end{verbatim}
\newpage

\item
Rewrite the following function, using only {\em recursion}
(no loop constructs):
\begin{verbatim}
function sum(N) : integer ;
var i : integer ;
begin
  {Precondition: N is any integer.}
  i := 0 ;
  repeat
    i := i + 1
  until (i*i) > N ;
  sum := i
end ;

\end{verbatim}

\end{enumerate}
\end{document}

