\documentclass{article}
\pagestyle{empty}

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

\noindent
This assignment is due at the start of class on Tuesday, Jan. 30.  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
${\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
Let the solution to the previous question be $f(n)$.  At this point you've shown
that the running time $T(n)$ satisfies the following:
$T(n)=f(n)$ when $n$ is a power of 3.  Now we want to extend this result to arbitrary
$n$.  
\begin{enumerate}
\item
Show the $f(\lceil \lceil n \rceil \rceil) = O(f(n))$.
\item
Use this result and the fact that $T(n)$ is monotonically increasing to argue that
$T(n)=f(n)$ for all $n$.
\end{enumerate}
\end{enumerate}

\item
Fill in the table with Y/N to the question $f(n)= {\cal X} (g(n))$ where
${\cal X}=O, \Omega, \Theta, o, \omega$.  Assume that $\epsilon, k$ and $c$ are
constants satisfying the following: $\epsilon > 0$,
$k > 1$,  and $c>1$.

\begin{tabular}{|l| l || l | l | l | l | l |} \hline
$f(n)$	& $g(n)$	& $O$	& $\Omega$	& $ \Theta $	& $o$	& $\omega$	 \\[.1 in]  \hline 
$n^{\epsilon}$ 	& $\log^k n$  	& & & & & \\[.1 in]  \hline
$n^k$	& $c^n$ 		& & & & & \\[.1 in] \hline
$n^{\lg c}$ 	& $c^{\lg n}$ 	& & & & & \\[.1 in] \hline
$n^k$	& $ n^{2k}$ 		& & & & & \\[.1 in] \hline
$n^k$	& $ (n/c)^k$ 		& & & & & \\[.1 in] \hline
$c^n$	& $ c^{n+k}$ 		& & & & & \\[.1 in] \hline
\end{tabular}


\item
Give asymptotic upper and lower bounds for the following recurrences. Your bounds
should be as tight as possible. You may
assume that $T(n)$ is constant for $n<=2$.
\begin{enumerate}
\item
$T(n)=T(n/3) + n$
\item
$T(n)= 7T(n/3) + n^2$
\item
$T(n)= 2T(n/4) + \sqrt{n}$
\item
$T(n)=T(\sqrt{n})+1$
\item
$T(n)=\sqrt{n}T(\sqrt{n})+n$
\end{enumerate}

\item
Construct a heap on the set $\{3,7,9,1,2\}$;  show the
heap as a binary tree as well as an array.  Show the 
heap after each of the following successive operations:  Insert $4$, Extract-min,
Insert $1$.

\end{enumerate}


\end{document}

