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

\begin{center}
\Large{\bf Problem Set 1 (due April 21)}
\end{center}

\bigskip

{\bf 1. (10 points)} Let 
\[
p(n) = \sum_{i = 0}^{d} a_i n^i
\]
be a degree-$d$ polynomial in $n$, where $a_0$ through $a_d$ are arbitrary
real constants and $a_d > 0$.  Using the definition of $\Theta$-notation,
prove that $p(n) = \Theta(n^d)$.

{\bf 2. (10 points)} Arrange the following functions in order from the slowest
growing function to the fastest growing function.  Briefly justify your
answer.  ({\em Hint:} It may help to express each function as a power of $2$
and then compare.)

\[ 
(\lg n)^{\lg n} \hs (\frac{3}{2})^{2n} \hs n^{100} \hs 2^{\sqrt{\lg n}}
\]

{\bf 3. (2 $\times$ 5 = 10 points)} Let $f(n)$, $g(n)$, and $h(n)$ be
asymptotically positive and monotonically increasing functions.  Prove
or disprove each of the following conjectures.
\begin{itemize}
\item[{\bf (a)}]
$f(n) + g(n) = \Theta(\max\{f(n), g(n)\})$.

\item[{\bf (b)}]
$f(n^2) = O((f(n))^2)$.
\end{itemize}

{\bf 4. (3 $\times$ 5 = 15 points)} Solve the following recurrences.
Assume that $T(n)$ is constant for $n \le 2$.  
\begin{itemize}
\item[{\bf (a)}]
$T(n) = 2T(n/4) + \sqrt{n}$.

\item[{\bf (b)}]
$T(n) = T(\sqrt{n}) + 1$.

\item[{\bf (c)}] $T(n) = T(\alpha n) + T((1 - \alpha)n) + n$, where $\alpha$
is a real constant in the range $0 < \alpha < 1$.  ({\em Hint:} Use a
recursion tree.)
\end{itemize}

{\bf 5. (15 points)} Problem~4--7, page 75.

{\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)$.

{\bf 7. (8 + 9 + 8 = 25 points)} The worst-case running time of both insertion
sort and quicksort is $\Theta(n^2)$.  Quicksort is considered an efficient
sorting algorithm because the average-case running time of quicksort (assuming
that all orderings are equally likely) is $\Theta(n \lg n)$.  In this
exercise, we take a closer look at insertion sort.  (For the pseudocode of
insertion sort, you may refer to your class notes or to Section 1.2 of the
textbook.)

Let $A[1..n]$ be an array of $n$ distinct numbers.  If $i < j$ and $A[i] >
A[j]$, then we say that the pair $(i,j)$ is an {\em inversion}\/ of $A$.

\begin{enumerate}
\item[{\bf (a)}] 
If $T(A)$ is the running time of insertion sort on input $A$ and $I(A)$ is the
number of inversions in $A$, then prove that $T(A)$ is $\Theta(I(A) + n)$.

\item[{\bf (b)}]
Show that if $A$ is a random permutation chosen uniformly at random
from the set of all $n!$ permutations, then the expected number of
inversions is $\Theta(n^2)$.  Using part~(a), derive a tight bound on the
expected running time of insertion sort on a random permutation.

\item[{\bf (c)}]
Using part~(a), solve Exercise 8.4--4, page 167.
\end{enumerate}

\end{document}

