\documentclass{article}
\pagestyle{empty}

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

\noindent
This is an optional assignment.  Any points you earn on this assignment will
be used (at a 50\% discount) to augment your grades for earlier assignments.  To receive credit
for this assignment you must submit it by Tuesday, Feb. 6.  Your solutions must
be typeset.  You may NOT work with your classmates to complete this assignment.
\vspace{.2 in}
\begin{enumerate}
\item

Order the following functions by inreasing rate of growth.  Indicate any equivalence
classes you find:
\begin{displaymath}
\begin{array}{lllll}
\log_3 n^3 & n^2 + \log n & n^2 \lg n & \lg^2 n &  2 \uparrow \uparrow (n) \\
2 \uparrow \uparrow (2n) & 3^{\log_5 n}	& n^2  & (\lg n)^{\lg n} &  n/\lg n
\end{array}
\end{displaymath}
\item
For each of the following pair $f(n)$ and $g(n)$ state whether or not (i) $f(n)=O(g(n))$, (ii) $f(n)= o(g(n))$,
(iii) $f(n)=\Omega(g(n))$, (iv) $f(n)=\omega(g(n))$, (v) $f(n)=\theta(g(n))$.
\begin{enumerate}
\item
$f(n)=n^2+n$ and $g(n)=n^3 - n^2$
\item
$f(n)=n^2$ and $g(n)=f(2n)$
\item
$f(n)=n!$ and $g(n)=f( 2 \lceil n/2 \rceil)$
\end{enumerate}
\item
State whether the following are true or false. You should assume that $f$ and $g$ are 
monotonically-increasing positive-valued functions on the natural numbers.
\begin{enumerate}
\item
If for every positive integer $n$, algorithm $\cal A$ performs $n^3-n$ steps on some input of
size $n$ then $\cal A$ is $O(n^3)$.
\item
If $f(n)/g(n)=2$ for even values of $n$ then $f(n) \not= \omega(g(n))$.
\item
If $f(n)=o(g(n))$ then $f(n)=O(g(n))$.
\item
If $f(n)=O(g(n))$ then $f(n)=o(g(n))$.
\item
If $\log(f(n))=O(\log(g(n))$ then $f(n)=O(g(n))$.
\item
If $2^{f(n)} = O(2^{g(n)})$ then $f(n)=O(g(n))$.
\end{enumerate}
\item
Algorithm ${\cal A}$ works on inputs of size $n=2 \uparrow \uparrow (m)$, $m=0,1,...$;  i.e. towers
of $2$.
On an input of $n=1$ the algorithm performs a constant number of steps.
On an input of size $n=2 \uparrow \uparrow (m)$, $m>0$, ${\cal A}$ makes $n/lg(n)$ recursive
calls, each on an instance of size $\lg(n)$.  It then performs an additional
$cn$ steps to produce its output.  
\begin{enumerate}
\item
Write the recurrence relation of the running time.
\item
Consider the work tree for
${\cal A}$ on input of size $n=2 \uparrow \uparrow (m)$.
\begin{enumerate}
\item
What is the input size at level $i$, where the root is at level $0$?
\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 in the work tree?
\item
Write a summation that represents the running time.
\end{enumerate}
\item
What is the running time of the algorithm?

(Note:  Recall the notation for the $i$th iterated log of $n$ is $lg^{(i)}n$;  i.e.
 $lg^{(0)}n = n$ and for $i>0 , \;lg^{(i)}n = lg (lg^{(i-1)}n)$.
This may be useful.)
\end{enumerate}

\item
Compute the running time of the following algorithm.  (Note:  As its name suggests,
the boolean function odd$(i)$ returns
true if $i$ is odd and false if $i$ is even.)

\noindent {\tt algorithm} veryodd($n$)
\begin{list}{}{}
\item {\hskip .2in \tt for $i=1$ to $n$ do \hfill}
\item {\hskip .4in \tt if {\rm odd}$(i)$ then \hfill}
\item {\hskip .6in \tt begin \hfill}
\item {\hskip .8in \tt for $j=i$ to $n$ do $x\leftarrow x+1$ \hfill}
\item {\hskip .8in \tt for $j=1$ to $i$ do $y\leftarrow y+1$ \hfill}
\item {\hskip .6in \tt end \hfill}
\item {\hskip .2in \tt end \hfill}
\end{list}
{\tt end algorithm}

\item
Give asymptotically tight bounds for the following recurrences.
\begin{enumerate}
\item
$f(n)=3f(n/2)+\sqrt{n}$
\item
$f(n)=f(9n/10)+n$
\item
$f(n)=f(\sqrt{n}) + n$
\end{enumerate}




\end{enumerate}
\end{document}

