\documentclass{article}
\pagestyle{empty}

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

\noindent
This assignment is due at the start of class on Thursday, Jan. 25.  You may collaborate
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.  This assignment is worth 100 points (75 points if handwritten).  


\vspace{.2 in}

\begin{enumerate}
\item
Algorithm ${\cal A}$ operates on inputs of size $b^m$ for $m=0,1,\ldots$.  On input
of size $1$ ${\cal A}$ makes $c$ steps.
On input of size $n>1$ algorithm ${\cal A}$ makes $a$ recursive calls, each on input of size
$n/b$.  Algorithm ${\cal A}$ then takes $f(n)$ steps to construct its solutions based on the
solutions to the recursive calls.  
Write the recurrence relation for the running time
of ${\cal A}$ for the following cases.
\begin{enumerate}
\item
$a=3, b=4, f(n)=cn^{\frac{3}{2}}$
\item
$a=4, b=3, f(n)=cn \log_b n$
\end{enumerate}
\item
Draw the work tree for $m=0,1,2$ for algorithm ${\cal A}$, case (i).
Answer the following questions about the work tree for input size $n=b^m$.  Assume the
root is at level 0.
\begin{enumerate}
\item
What input size is associated with a node at level $i$.
\item
What work is done at a node in level $i$.
\item
How many nodes are at level $i$.
\item
What is the total work done by the nodes at level $i$?
\item
How many levels are there?
\item
Write a finite series (summation) that represents the total work
done by the algorithm on input size $n$.
\end{enumerate}
\item
Repeat the previous problem for algorithm ${\cal A}$, case ii.  

\end{enumerate}
\end{document}

