\documentclass{article}
\pagestyle{empty}

\begin{document}
\begin{center}
{\LARGE CS140: Algorithms }\\
\vspace{.1 in}
{\Large Fall 2001}\\
\vspace{.3 in}
{\large Assignment 2}
\end{center}

\noindent
This assignment is due at the start of class on Monday, Sept. 17.  You may collaborate
in small groups with your classmates to complete this assignment but you should reference your collaborators.  You
also must thoroughly understand any solutions you submit 
and must do your own write-up of those solutions.  You may not refer to solutions
to assignments given in previous semesters of CS140.  This assignment is worth 100 points (75 points if handwritten).  


\vspace{.2 in}

\begin{enumerate}


\item
Order the following functions by increasing rate of growth.  Indicate any
equivalence classes you find.

\begin{displaymath}
\begin{array}{lllll}
\lg^*n          & \lg(\lg^*n)   & 2\uparrow \uparrow (\lg^*(n)) & 2^{\lg^*(n)}
        & (\lg n)! \\
\lg (n!)        & n^2           & 2n+\lg n      & (\lg n)^{\lg n}       & 2^{n/2
} \\
\log \log n     & 2^{\lg n}     & (\frac{3}{2})^n       & n^{1/ \lg n} & 5
\\
\lg (n^{\lg n}) & (\frac{1}{2})^n       & \sqrt{n}      & 2^{3 \uparrow \uparrow
 n}  & 4^n
\end{array}
\end{displaymath}


\item
${\cal A}$ is a divide and conquer algorithm with recurrence relation $T(n)=4T(n/3) + n$.
Answer the following questions about the work tree for ${\cal A}$
on input size $n=3^m$.
\begin{enumerate}
\item
What is the input size to a node at level $i$, where the root is at level $0$?
\item
How much work is done at a node at level $i$?
\item
How many nodes are at level $i$?
\item
What is the total amount of work done by the nodes at level $i$?
\item
The root is at level $0$.  What level are the leaves at?
\item
Write a series that represents the running time of the algorithm for inputs of size
$n=3^m$.
\item
Solve the series.
\item
Now prove that the big-O bound you obtain through the previous analysis
holds for all values of $n$.
\end{enumerate}

\item
Answer the work tree questions posed in the previous problem for each
of the recurrence shown below.  You may
assume that $T(n)$ is constant for $n<=2$.
\begin{enumerate}
\item
$T(n)=T(n/3) + n$
(Assume $n=3^m$ for some $m$.)
\item
$T(n)= 7T(n/3) + n^2$
(Assume $n=3^m$ for some $m$.)
\item
$T(n)= 2T(n/4) + \sqrt{n}$
(assume $n=4^m$ for some $m$.)
\item
$T(n)=T(\sqrt{n})+1$
(Assume $n=2^{2^m}$ for some $m$.)
\item
$T(n)=\sqrt{n}T(\sqrt{n})+n$
(Assume $n=2^{2^m}$ for some $m$.)
\end{enumerate}


\end{enumerate}


\end{document}

