\documentstyle[12pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\newcommand{\k}{{\it key}}
\newcommand{\twolists}{{\sc 2List-Select}}
\head{3390}{Analysis of Algorithms}{Winter 2000}{15 February 2000}{11}

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

{\bf Instructions.}
\begin{Itemize}
\item This is a 90 minute midterm, to be graded out of 100 points.
  There are five questions worth a total of 100 points and a bonus
  problem worth 15 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 & & 20 \\ \hline
2 & & 20 \\ \hline
3 & & 15 \\ \hline
4 & & 25 \\ \hline
5 & & 20 \\ \hline
Bonus & & 15 \\ \hline
Total & & 100 \\ \hline
\end{tabular}
\end{center}
}

\vfill

\newpage

{\bf Problem 1 (2 $\times$ 10 = 20 points) \hs} Consider the recurrence relation
\[T(n) = 4T(n/4) + f(n).\]
Derive a tight bound for $T(n)$ in each of the following two cases.
Assume that $T(n)$ is $\Theta(1)$ for $n \le 4$.
\begin{itemize}
\item[{\bf (a)}] $f(n) = n^2$.

\vfill

\item[{\bf (b)}] $f(n) = n\lg n$.

\vfill

\end{itemize}

\newpage
{\bf Problem 2 (2 $\times$ 10 = 20 points)\hs}
\begin{itemize}
\item[{\bf (a)}] Derive upper and lower bounds on the following summation
\[
\sum_{k = 1}^{n} k^r,\] where $r$ is a positive real constant.  

\vfill 

\item[{\bf (b)}] Prove or disprove: The height of every binary tree
  with $n$ nodes is $\Omega(\lg n)$.

\vfill

\end{itemize}

\newpage

{\bf Problem 3 (15 points)\hs} Describe an efficient algorithm that,
given a set $S$ of $n$ distinct numbers and a positive integer $k \le
n$, determines the $k$ numbers that are closest (in terms of the
absolute value of the difference) to the median of $S$.  The more
efficient your algorithm is in terms of its worst-case running time,
the more credit you will get.  Justify the running time of your
algorithm.

\newpage

{\bf Problem 4 (15 + 10 = 25 points)\hs} Suppose we are given
$k$ sorted lists, each consisting of $n$ elements.  The {\em
  multimerge}\/ problem is to merge the $k$ lists into a single sorted
list of length $nk$.
\begin{itemize}
\item[{\bf (a)}] Design an efficient comparison-based algorithm for
  the multimerge problem.  The more efficient your algorithm is in
  terms of its worst-case running time, the more credit you will get.
  Justify the running time of your algorithm.

\vfill
  
\item[{\bf (b)}] Using a decision-tree argument, derive a lower bound
  on the running time of any comparison-based algorithm for the multimerge
  problem.  ({\em Note:} You may make use of the fact that $\lg
  m!=m\lg m-\Theta(m)$.)

\vfill
\newpage
\end{itemize}

{\bf Problem 5 (20 points) \hs} Describe how to efficiently maintain a
dynamic set $S$ of integer keys that supports the operations {\it
  insert\/} (add a given key to $S$), {\it delete\/} (delete a given
key from $S$), {\it find\/} (determine whether a given key belongs to
$S$), and {\it max-run\/} (compute the length of the longest run of
consecutive integers in $S$).  (For example, if
$S=\{1,5,6,9,15,16,17,18,22\}$, then a call to {\it max-run\/} returns
$4$ since $15,16,17,18$ is the longest run of consecutive integers in
$S$.)  The operations {\it insert\/}, {\it delete\/}, and {\it find\/}
should run in $O(\log n)$ time, where $n = |S|$.  The operation {\it
  max-run\/} should run in $O(1)$ time.  ({\em Hint:} Make use of an
appropriately-augmented balanced binary search tree.)

\newpage

{\bf Bonus Problem (15 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.

\end{document}


