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

\begin{center}
\Large{\bf Problem Set 1 (due January 18)}
\end{center}

\bigskip

%%% A poorly worded question.  It's a little tricky since the a_i's form an infinite sequence. 
%%% One may ask whether their being constants implies that there is an infimum and a supremum
%%% for the sequence.

{\bf 1. (10 points)} Let
\[
f(n) = \sum_{i = 0}^{n} a_i 2^i,
\]
where $a_0$ through $a_n$ are arbitrary real constants and $a_n > 0$.
Using the definition of $\Theta$-notation, prove that $f(n) =
\Theta(2^n)$.

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

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

{\bf 3. (3 $\times$ 5 = 15 points)} Prove or disprove each of the
following conjectures.
\begin{itemize}
\item[{\bf (a)}]
If $f(n)$ is a polynomial in $n$, then $f(n^2)$ is $\Theta((f(n))^2)$.

\item[{\bf (b)}] Let $f(n)$, $g(n)$, and $h(n)$ be asymptotically
  positive and monotonically increasing functions.  If $g(n) =
  \Theta(h(n))$, then $f(n)^{g(n)} = \Theta(f(n)^{h(n)})$.
  
\item[{\bf (c)}] Let $f(n)$ and $g(n)$ be asymptotically positive and
  monotonically increasing functions.  Then, $f(n) + g(n) =
  O(\max\{f(n), g(n)\})$.
\end{itemize}

{\bf 4. (5 + 10 + 5 + 5 = 25 points)} Problem 1--2, page 17.

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

\item[{\bf (b)}] $T(n) = 4T(n/4) + n^2$.

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

\item[{\bf (d)}] $T(n) = T(n^{2/3}) + 5$.
\end{itemize}

{\bf 6. (5 + 5 + 10 = 20 points)} Problem 8--4, page 169.  In
part~(c), your modification must maintain the expected $\Theta(n \lg
n)$ running time of the algorithm.
\end{document}

