
\documentstyle[11pt,twoside,amstex,psfig]{article}

\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\raggedbottom

\input{macros-course}
\iffalse
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\fi
%\newtheorem{fact}{Fact}
\begin{document}

\handout{teamprobs5}{Problems for Recitation 5}{October 9, 1998}

\begin{problems}

\problem We begin with two large glasses.  The first glass contains a pint
of water, and the second contains a pint of wine.
We pour $1/3$ of a pint
from the first glass into the second, stir up the wine/water mixture in
the second glass, and then pour $1/3$ of a pint of the mix back into the
first glass.  We now repeat this pouring back-and-forth process a total of
$n$ times.
\bparts

\ppart
Describe a closed form formula for the amount of wine in the first glass
after $n$ back-and-forth pourings.

\ppart
What is the limit of the amount of wine in each glass as $n$ approaches infinity?
\eparts

\problem
\bparts
\ppart Give an example of functions $f,g:\naturals\to\naturals$ such that
neither $f = O(g)$ nor $g = O(f)$.  Prove it.


\ppart 
Prove or give a counterexample:
If $f_1,f_2,\dots$ is a sequence of functions from $\naturals$ to
$\naturals$ such that $f_i(n) = O(1)$ for all $i\geq 1$, then 
\[\sum_{i=1}^n f_i(n) = O(2^n).\]
\eparts
\problem
\bparts
\ppart Show that the Master Theorem does not apply to
\[S(m) = S(m/2) + (\log m)^2.\]

\ppart Find a $\Theta()$ bound for $S$ anyway.

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

\end{problems}
\end{document}
