\documentclass{article}
\begin{document}


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

\vspace{1 in}
${\cal A}$ is a divide and conquer algorithm  that works on inputs of
size $n=3^m$ for $m=0,1,\ldots$.  On an input of size $1$ the algorithm
takes a constant $c$ number of steps.  On inputs of size $n=3^m$, $m>1$
the algorithm makes $4$ recursive calls, each on size $n/3 = 3^{m-1}$.
In addition the algorithm takes $n^3$ steps to compute its solution  
based on the solutions to the recursive calls.
Draw the work trees for this algorithm for $m=0,1,2$.

\vspace {2 in}

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$.
\end{enumerate}


\end{document}
