\documentstyle[12pt,handout]{article}
\begin{document}
\input{epsf}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\input{courseMacros}

\newcommand{\heapsize}{\mbox{{\em heap-size}}}
\newcommand{\len}{\mbox{{\em length}}}
\newcommand{\heapify}{\mbox{{\sc Heapify}}}

\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 2001}{14 February 2001}{15}

\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, and a bonus subproblem worth 20 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 & & 40 \\ \hline
3 & & 35 \\ \hline
4 & & 80 \\ \hline
Bonus & & 20 \\ \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} For each of the
following statements, indicate whether it is true.  In each case,
justify your answer.
\begin{itemize}
\item[{\bf (a)}] $n^{3/2} = O(n \lg n)$.

\vfill 

\item[{\bf (b)}]
The following recurrence relation can be solved by the Master theorem.
\[T(n) = 2T(n/2) + n\lg n\]
\vfill

\item[{\bf (c)}] 
The average of any set of $n$ numbers is always at least half the
median.  (You may assume that $n$ is odd.)

\vfill
\end{itemize}

\newpage

{\bf Problem 2. (40 points) \hs} Determine the heap that is obtained
after calling {\sc Build-Heap} on the array $A = [\mbox{V, A, L, E, N, T,
I}]$, where the ordering among the letters is lexicographic.  For
instance, $\mbox{H} < \mbox{L}$.  The pseudocode for {\sc Build-Heap} follows.  (You
may simply state the final result without any additional
justification.)

\begin{tabbing}
{\sc Build-Heap}$(A)$\\
1. \= $\heapsize[A] \leftarrow \len[A]$\\
2. \> \algfor\ \= $i \leftarrow \lfloor \len[A]/2 \rfloor$ \algdownto\
$1$\\
3. \> \> $\heapify(A,i)$
\end{tabbing}

\newpage

{\bf Problem 3. (35 points) \hs} Derive a tight bound for the
following recurrence relation.  Assume that $T(n)$ is $\Theta(1)$ for
$n\le 4$.

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


\newpage

{\bf Problem 4. (40 + 40 =  80 points + 20 bonus points)}

Consider a set $S$ of $n\geq 2$ distinct integers given in unsorted
order.  Each of the following three problems asks you to give an
algorithm to determine two distinct integers $x$ and $y$ in the set
$S$ that satisfy a stated condition.  Briefly describe your algorithm
and justify its running time.
\begin{itemize}
\item[{\bf (a)}] In $O(n\log n)$ time, determine $x,y\in S$
such that $x\neq y$ and
\[
|x-y|\leq |w-z|
\]
for all $w,z\in S$ such that $w\neq z$.  That is, determine two
numbers that are as close together as any two numbers in the set.
\vfill

\newpage 

\item[{\bf (b)}] In $O(n)$ expected time, determine $x,y\in
S$ such that $x\neq y$ and
\[
x+y= Z
\]
where $Z$ is given, or determine that no such pair exists.  {\em
Hint:} Use hashing.
\vfill

\item[{\bf (c)}] {\bf (Bonus problem)} \hs
 In $O(n)$ time, determine $x, y \in S$ such that
\[
|x - y| \le \frac{1}{n-1}\left(\max(S) - \min(S)\right),
\]
i.e., determine any two numbers that are at least as close together as
the average distance between consecutive numbers in the sorted order.
\vfill
\end{itemize}

\end{document}

