\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}{Winter 2000}{18 January 2000}{7}

\begin{center}
\Large{\bf Problem Set 2 (due February 1)}
\end{center}

\bigskip 

{\bf Reminder:} Problem~6 of Problem Set~1 is also due with
this problem set.  

\bigskip

{\bf 1. (2 + 3 + 10 + 5 = 20 points)} Problem 1--3, page 18.

{\bf 2. (2 + 8 + 5 = 15 points)} A {\em bitonic}\/ sequence is a
sequence of numbers that monotonically decreases and then
monotonically increases.  That is, a sequence $X = x_1, x_2, \ldots,
x_n$ is bitonic if there exists a $t$ in $[1, n]$ such that $x_{i+1} <
x_i$ for $1 \le i < t$ and $x_{i+1} > x_i$ for $t \le i < n$.
\begin{Itemize}
\item[{\bf (a)}]
Give an $O(1)$ time algorithm to find the maximum of a given bitonic sequence.

\item[{\bf (b)}]
Give an $O(\lg n)$ time algorithm to find the minimum of a given bitonic
sequence of length $n$.  Briefly justify the correctness of your algorithm.

\item[{\bf (c)}]
Give an $O(\lg n)$ time algorithm to find the median of a given bitonic
sequence.  ({\em Hint:} Use part~(b).)
\end{Itemize}

{\bf 3. (11 points)} Exercise~10.3--9, page 192.

{\bf 4. (10 + 10 = 20 points)} 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}

{\bf 5. (2 + 5 + 5 + 5 + 2 + 5 = 24 points)} Problem 13--3, page 260.

{\bf 6. (10 points)} Show that any arbitrary $n$-node binary search
tree can be transformed into any other arbitrary $n$-node binary
search tree using $O(n)$ rotations.  ({\em Hint:}\/ First show that at
most $n - 1$ right rotations suffice to transform the tree into a
right-going chain.)

{\bf Bonus Problem (10 points)} Design and analyze an efficient
algorithm to select a key of a given rank from a set of $m+n$ keys
given in the form of two sorted lists, one of length $m$ and the other
of length $n$.  For convenience, you may assume that the $m+n$ keys
are all distinct.  ({\em Hint:}\/ A running time of
$O(\log\min\{m,n\})$ is achievable.)

\end{document}

