\documentstyle[12pt,handout]{article}
\begin{document}
\input{macros}
\input{epsf}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\input{/home/rraj/Courses/1390/W00/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}

\newcommand{\ins}{\mbox{{\sc Insert}}}
\newcommand{\del}{\mbox{{\sc Delete}}}
\newcommand{\search}{\mbox{{\sc Search}}}
\newcommand{\mini}{\mbox{{\sc Minimum}}}
\newcommand{\maxi}{\mbox{{\sc Maximum}}}
\newcommand{\suc}{\mbox{{\sc Successor}}}
\newcommand{\pred}{\mbox{{\sc Predecessor}}}
\newcommand{\subtreemin}{\mbox{{\sc SubtreeMin}}}
\newcommand{\rt}{\mbox{{\it root}}}

\head{1390}{Algorithms}{Winter 2000}{15 February 2000}{12}

\begin{center}
\Large{{\bf Midterm}} 
\end{center}

{\bf Instructions.}
\begin{Itemize}
\item This is a 60 minute midterm. It has four problems worth a total
  of 200 points.

\item
Read all the problems through first and attack them in the order that allows
you to make the most progress.

\item While describing an algorithm, you may use any of the algorithms
  covered in class or in the text as a subroutine.  You need to
  provide a proof of correctness and/or an analysis of the running
  time only for those problems where they are explicitly required.

\item
Show your work, as partial credit will be given.  If you need extra space, use
the blank facing page.  

\item
Best of luck!
\end{Itemize}

\vfill

{\Large
\begin{center}
\begin{tabular}{||c|c|c||}\hline
Question & Score & Maximum \\ \hline
1 & & 45 \\ \hline
2 & & 60 \\ \hline
3 & & 40 \\ \hline
4 & & 55 \\ \hline
Total & & 200 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

\begin{center}
{\bf Name:} {\vrule height0.4pt width3in}
\end{center}
\vfill
\vfill


\newpage

{\bf Problem 1.  (3 $\times$ 15 = 45 points) \hs} 
\begin{itemize}
\item[{\bf (a)}] Arrange the following functions in order from the
  slowest growing function to the fastest growing function.  You may
  simply state the answer without any additional justification.

\[ \lg n \hs (\lg \lg n)^2 \hs \sqrt{n} \]

\vfill 

\item[{\bf (b)}] A {\em max-heap\/} is a heap in which the value
  stored at every node is less than the value stored at the parent of
  the node.  Is it true that the minimum element in a max-heap is
  always stored at a leaf node?  Briefly justify your answer. (Assume
  that all the keys in the heap are distinct.)

\vfill
\item[{\bf (c)}] For which of the three open-addressing schemes,
  namely, linear probing, quadratic probing, and double hashing, is
  the following statement true?  For any two distinct keys $k_1$ and
  $k_2$, if $h(k_1) = h(k_2)$, then the probe sequence for $k_1$ is
  the same as that for $k_2$.  Here, $h$ is the primary hash function.
  Briefly justify your answer.  \vfill
\end{itemize}

\newpage

{\bf Problem 2. (30 + 30 = 60 points) \hs} 
\begin{itemize}
\item[{\bf (a)}] Derive a tight bound for the following recurrence
  relation.  Assume that $T(n)$ is $\Theta(1)$ for $n\le 3$.

\[ T(n) = T(n/2) + T(n/3) + 2n.\]

\vfill

\newpage

\item[{\bf (b)}]
Consider the following sorting algorithm.

\begin{tabbing}
{\sc New-Sort}$(A,p,r)$ \hs (to sort $A[p..r]$)\\
1. \= $n = r - p + 1$\\
2. \> If $n > 1$ \= then\\
3.\> \> Find elements $m_1$ and $m_2$ of rank $\lceil n/3 \rceil$ and $\lceil 2n/3 \rceil$, respectively\\
\> \> using the linear-time selection algorithm ({\sc Select})\\
4.\>\> Partition $A$ into three parts $A[p..q]$, $A[q+1..s]$, and $A[s+1..r]$ such that\\
\> \>  every element in $A[p..q]$ is at most $m_1$, every element in $A[q+1..s]$ is greater\\
\> \>  than $m_1$ and at most $m_2$, and every element in $A[s+1..r]$ is greater than $m_2$\\
5.\>\> {\sc New-Sort}$(A,p,q)$\\
6.\>\> {\sc New-Sort}$(A,q+1,s)$\\
7.\>\> {\sc New-Sort}$(A,s+1,r)$
\end{tabbing}

Derive and solve a recurrence for the worst-case running time of {\sc
  New-Sort} on an array of $n$ elements.  You may ignore floors and
ceilings in your calculation.  Furthermore, you may afssume that all
the elements in the input array are distinct.
\end{itemize}

\newpage

{\bf Problem 3. (40 points) \hs} Suppose we are given positive integers $a$
and $n$ and asked to compute $a^n$, that is, the $n$th power of $a$.
The simplest algorithm performs $n - 1$ multiplications by computing
$a \times a \times \ldots \times a$.  Design a divide-and-conquer
algorithm that computes $a^n$ using $O(\lg n)$ multiplications.
Justify the running time of the algorithm.

\vfill

\newpage

{\bf Problem 4. (20 + 35 = 55 points) \hs} 

\begin{itemize}
\item[{\bf (a)}] Label the following binary tree with numbers from the set $\{6,
  22, 9, 14, 13, 1, 8\}$ so that it is a legal binary search tree.

\vspace{.1in}

\centerline{\epsfxsize=4in \epsffile{bst.eps}}

\item[{\bf (b)}] Recall that all of the binary search tree operations studied in
  class, namely, \ins, \del, \search, \maxi, \mini, \suc, and \pred\ 
  take $O(h)$ time in the worst-case, where $h$ is the height of the
  binary tree.  In this exercise, we would like to augment the binary
  search tree in such a way that the operation \mini\ can be
  calculated in $O(1)$ time.
  
  We add a new field called $\subtreemin[x]$, which stores for each
  node $x$ the minimum key value among all of the nodes in the subtree
  rooted at $x$.  This way, for a given binary search tree $T$, we can
  perform $\mini[T]$ by simply returning $\subtreemin[\rt[T]]$.
  
  Describe how to modify the \ins\ and \del\ operations so as to
  maintain the $\subtreemin[\cdot]$ field and yet keep the worst-case
  running time of the operations to be $O(h)$.
\end{itemize}
  
\end{document}

