\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 1999}{11 January 1999}{5}

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

\bigskip

{\bf 1. (8 points)} We have seen the following bound in class.
\[\sum_{1 \le i \le n} i^2 = \Theta(n^3).\]
Derive an asymptotically tight bound on the summation 
\[\sum_{1 \le i\le n} i^c,\]
where $c \ge 0$ is a given constant real number.

{\bf 2. (12 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 plot the functions
and obtain an estimate of their relative growth rates.  It may also
help to express each function as a power of $2$ and then compare.)

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


{\bf 3. (3 $\times$ 6 = 18 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(\min\{f(n), g(n)\})$.

\item[{\bf (b)}]
If $f(n) = O(h(n))$ and $g(n) = \Omega(h(n))$, then $f(n) = O(g(n))$.

\item[{\bf (c)}]
$f(n^2) = \Omega((f(n))^2)$.


\junk{
\item[{\bf (c)}]
$f(n) + g(n) = \Theta(\min\{f(n), g(n)\})$.
}

\end{itemize}

{\bf 4. (3 $\times$ 6 = 18 points)} Solve the following recurrences.
Assume that $T(n)$ is constant for $n \ge 3$.  Make your bounds as
tight as possible, and justify your answers.
\begin{itemize}
\item[{\bf (a)}] 
$T(n) = T(n - 1) + \lg n$.

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

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

{\bf 5. (2 $\times$ 7 = 14 points)}  Parts~(a) and~(b) of Problem~5--2.

\end{document}
