\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}

\head{3390}{Analysis of Algorithms}{Spring 1999}{28 April 1999}{12}

\begin{center}
\Large{\bf Problem of the Week -- 4}
\end{center}

\bigskip
Let the {\em multi-selection problem\/} be defined as follows. The input is a
set $S$ of $n$ distinct keys drawn from some totally ordered universe, and a
set of $k+1$ integers $r_i$ such that $1=r_0<r_1<\cdots<r_k=n+1$.  The output
is a partition of $S$ into $k$ sets $S_0,\ldots,S_{k-1}$ such that $S_i$ is
the set of all keys with ranks greater than or equal to $r_i$ and strictly
less than $r_{i+1}$.
\begin{Enumerate}
\item[(a)] Give an $O(n\lg k)$ time comparison-based algorithm for the
multi-selection problem.  You may assume for simplicity that $k$ is a power of
$2$.

\item[(b)] 
Show that any comparison-based algorithm for the multi-selection problem
requires $\Omega(n\lg k)$ comparisons in the worst case.  You may assume for
simplicity that $n$ is evenly divisible by $k$.  ({\em Hint:} You may make use
of the fact that $\lg m!=m\lg m-\Theta(m)$.)
\end{Enumerate}
\end{document}
