\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}{21 April 1999}{9}

\begin{center}
\Large{\bf Problem Set 2 (due May 5 -- no late homework)}
\end{center}

\bigskip

{\bf 1. (3 + 3 + 9 = 15 points)}\hs Consider a set $S$ of $n$ distinct numbers
given in unsorted order.  Each of the following three problem parts asks you
to give an algorithm to determine two distinct numbers $x$ and $y$ that
satisfy a stated condition.  For each part, describe your algorithm and then
briefly justify the correctness and the running time of the algorithm.
\begin{enumerate}
\item
In $O(n)$ time, determine $x, y \in S$ such that $|x - y|$ is maximum.

\item
In $O(n \lg n)$ time, determine $x, y \in S$ such that $|x - y|$ is minimum.

\item
Let $M$ and $m$ denote the maximum and minimum numbers in $S$, respectively.
In $O(n)$ time, determine $x, y \in S$ such that $x$ and $y$ appear
consecutively in the sorted order and
\[|x - y| \ge \frac{1}{n-1}(M - m).\]
That is, determine any two numbers that appear consecutively in the sorted
order and are at least as far apart as the average distance between
consecutive numbers in the sorted order.

({\em Hint:} Use divide and conquer.)
\junk{
The {\em exact}\/ average distance between consecutive numbers in the sorted
order equals 
\[\frac{1}{n-1}(M - m).\]
 For {\bf 5 bonus points}, give an $O(n)$ time algorithm to determine $x, y
\in S$ such that $x$ and $y$ appear consecutively in the sorted order and
\[|x - y| \le \frac{1}{n-1}(M - m).\]
}
\end{enumerate}

{\bf 2. (5 $\times$ 4 = 20 points)}\hs Problem~7--2, page 152.

{\bf 3. (4 points)}\hs Give a constant time algorithm to find the fifth largest
element from a heap of $n$ distinct elements.

{\bf 4. (4 $\times$ 4 = 16 points)}\hs Problem~13--1, page 259.

{\bf 5. (5 + 7 + 10 + 8 = 30 points)}\hs Problem~19--2, page 399.

{\bf 6. (15 points)}\hs Consider a set of $n$ rectangular paving stones where the
$i$th stone is $l_i$ units long and $w_i$ units wide, $l_i\geq w_i\geq 1$.
Assume that paving stone $i$ can be stacked on top of paving stone $j$ iff
$l_i\leq l_j$ and $w_i\leq w_j$.  Give an efficient algorithm for computing
the maximum number of paving stones that can be stacked together, and analyze
the asymptotic running time of your algorithm.  ({\em Hint:}\/ Use dynamic
programming.)
\end{document}
