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

\head{3390}{Analysis of Algorithms}{30 September 1998}{3}

\begin{center}
\Large{\bf Problem Set 1 (due October 14)}
\end{center}

\bigskip
{\bf 1.} (3 $\times$ 3 = 9 points) Parts~(d),~(g), and~(h) of Problem 2--4,
page 39.

{\bf 2.} (4 $\times$ 5 = 20 points) Parts~(d),~(e),~(f), and~(h) of
Problem~4--1, page 72.

{\bf 3.} (10 points) Give an $O(n \log n)$ time algorithm that determines
whether two given lists $A$ and $B$, each consisting of $n$ numbers, have a
number in common.

{\bf 4.} The {\em Fibonacci numbers}\/ are defined by the following
recurrence: 
\begin{eqnarray*}
F_0 & = & 0\\
F_1 & = & 1, \mbox{ and}\\
F_i & = & F_{i-1} + F_{i-2} \mbox{ for } i \ge 2.
\end{eqnarray*}

\begin{Enumerate}
\item[(a)] (5 points) 
Prove that for any $n \ge 2$, $F_n$ equals $A^{n-1}_{1,1}$, where $A^n$ is the
$n$th power of the following matrix:
\[
A = \left( 
\begin{array}{cc}
1 & 1\\ 
1 & 0
\end{array}
\right).
\]

\item[(b)] (10 points)
Use part~(a) to obtain an algorithm that computes $F_n$ in $O(\log n)$ time.
\end{Enumerate}

{\bf 5.} Let $n$ balls be thrown independently and uniformly at
random into $n$ bins.  
\begin{Enumerate}
\item[(a)] (5 points)
Prove that the expected number of empty bins is at most $n/e$. ({\em Hint:}\/
For every positive integer $a$, $(1 - 1/a)^a \le 1/e$.)

\item[(b)] (11 points) Prove that if $n \ge 16$, the probability that there
exists a bin that receives at least $4 \lg n/\lg \lg n$ balls is at most
$1/n$.  ({\em Hint:}\/ Find the probability that a given bin receives at least
$k$ balls for a given positive integer $k$.  Also, the following inequality
may be helpful.  For all positive integers $a$ and $b$ such that $a \ge b$, we
have ${a \choose b} \le (ea/b)^b$.)
\end{Enumerate}

{\bf 6.} (6 + 6 + 3 = 15 points) Problem~8--3, page 169.  For part~(c), use
the fact that worst-case running time of heapsort is $\Theta(n \log n)$.

%%% This was not a satisfactory question, at least the way it was stated.  
%%% It is not clear whether the students got the point across.
{\bf 7.}  Consider the following randomized procedure {\sc
New-Partition} for partitioning a given array $A$ of $n$ distinct
integers into two subarrays $A_{\ell}$ and $A_{h}$ of total length
$n$: (i) Find the maximum number $M$ and the minimum number $m$ in the
array $A$.  (ii) Select a random integer $r$ in the range $[m, M]$.
(iii) Partition $A$ around the value $r$ into subarrays $A_{\ell}$ and
$A_{h}$ such that each element in $A_{\ell}$ is at most $r$ while each
element of $A_{h}$ is greater than $r$.

\begin{Enumerate}
\item[(a)] (2 points) What is the running time of {\sc New-Partition}?

\item[(b)] (10 points) Prove that the probability that $A_{\ell}$ has exactly
$n - 1$ elements can be made arbitrarily close to 1 by choosing $A$
appropriately.

\item[(c)] (3 points) Based on~(a), discuss how the expected running time of
randomized {\sc Quicksort} will change if it uses {\sc New-Partition} instead
of the randomized partition procedure studied in class.
\end{Enumerate}
\end{document}
