\documentstyle[11pt,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}{8 February 2000}{9}

\begin{center}
\Large{\bf Practice Problems for Midterm}
\end{center}

\bigskip 

{\bf 1.} Let $f(n)$ and $g(n)$ be two asymptotically positive and
monotonically increasing functions.  Prove or disprove the following
statement: $f(n) = \Theta(g(n))$ if and only if $\log (f(n)) =
\Theta(\log(g(n)))$.

{\bf 2.} Solve the following recurrences.  In each case, assume that $T(n)$ is
constant for $n \le 3$.
\begin{itemize}
\item[{\bf (a)}]
$T(n) = T(n/3) + T(2n/3) + n^2$.
\item[{\bf (b)}]
$T(n) = 3T(n/2) + n \lg n$.
\end{itemize}

{\bf 3.} Let ${\cal A}$ denote a comparison-based selection algorithm
that makes at most $10n$ comparisons in the worst case when applied to
any given set of $n$ keys, regardless of the rank of the key being
sought.  Let $S$ denote a set of $2^k$ distinct keys for some
nonnegative integer $k$.
\begin{enumerate}
\item[(a)] 
Prove that for $k\geq 1$, algorithm ${\cal A}$ can be used to
partition $S$ into a ``low half'' (i.e., the $2^k/2=2^{k-1}$ lowest
keys) and a ``high half'' using at most $(11)2^k$ comparisons.

\item[(b)] 
Prove that for $k\geq 2$, algorithm ${\cal A}$ can be used to
partition $S$ into ``quartiles'' (i.e., the lowest $2^k/4=2^{k-2}$
keys, the next-lowest $2^{k-2}$ keys, and so on) using at most
$(22)2^k$ comparisons.

\item[(c)] 
Let $m\geq 0$ be given.  Prove that for $k\geq m$, algorithm ${\cal
A}$ can be used to partition $S$ into ``$2^m$-tiles'' (i.e., the
lowest $2^{k-m}$ keys, the next-lowest $2^{k-m}$ keys, and so on)
using at most $(11m)2^k$ comparisons.

\item[(d)] 
Setting $m=k$ in the result of part~(c), we see that ${\cal A}$ can be
used to sort $S$ using at most $(11k)2^k$ comparisons.  Is this number
of comparisons optimal to within a constant factor?  Hint: Let
$n=|S|=2^k$, and express the number of comparisons as a function of
$n$.
\end{enumerate}

{\bf 4.} Suppose we are using a binary search tree to maintain a
dynamic set.  Give a sequence of $n$ insert requests for which the
binary search tree obtained is a line.  Give a sequence of $n$ insert
requests for which the binary search tree obtained is a complete
binary tree.  (For the second part, you may assume that $n$ is of the
form $2^k - 1$.)

{\bf 5.} Describe how to efficiently maintain a dynamic set $S$ of
integer keys that supports the operations {\it insert\/} (add a given
key to the set $S$), {\it delete\/} (delete a given key from the set
$S$), {\it find\/} (determine whether a given key belongs to the set
$S$), and {\it min-gap\/} (compute the absolute value of the
difference between the two closest integers in $S$).  (For example, if
$S=\{1,5,9,15,18,22\}$, then a call to {\it min-gap\/} returns
$18-15=3$ since 15 and 18 are the two closest integers in $S$.)  The
operations {\it insert\/}, {\it delete\/}, and {\it find\/} should run
in $O(\log|S|)$ time.  The operation {\it min-gap\/} should run in
$O(1)$ time.  Hint: Make use of an appropriately-augmented balanced
binary search tree.
\end{document}
