\documentstyle[12pt,twoside,amsfonts,amstex]{article}
\input{macros-course-tutorials}

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial9}{Problems for Tutorial 9}{April 14, 1997}

\begin{problems}

\problem
Find a $\Theta(\cdot)$ bound for
\[
T(n) = T(\sqrt{n}) + \lg \lg n.
\]
The base condition is $T(1)=1$.

\problem 
Consider the linear recurrence \\
$T(n) = \sum_{i=1}^d a_{i}T(n/2^i) + G(n)$

\begin{itemize}
\item Find a transformation $n \rightarrow m$ that will convert this problem io a difference equation of the form \\
$f(m) = \sum_{i=1}^d a_{i}f(m-i) + g(m)$ \\

\item Apply your results to find the solution of the recurrence relation \\
$T(n) = T(n/2) + 2T(n/4) + nlogn$

\end{itemize}

\problem 

Compute the following limits.

\begin {itemize}
\item $\sum_{i=1}^{\infty} \frac {1}{i(i+1)}$.
\item $ \lim_{n \rightarrow \infty}  1/n + 1/(n+1) + \ldots + 1/2n$
\item $ \lim_{n \rightarrow \infty} \frac{n}{2^n} \sum_{k=1}^{n}\frac{2^k}{k}$
\end{itemize}


% \problem 

% Prove that the stacking arrangement shown in class is optimal for
% producing the most overhang with a given number of books. That is,
% given $n$ books, show that the most overhang that can be produced is
% $H_n$, the $n$th harmonic number.\\



\end{problems}

\end{document}

