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

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

\raggedbottom

\input{macros-course}

\newcommand{\recn}[3]
{\setcounter{problemsetnum}{#1}
\handout{recprobs#1}{Problems for Recitation #1}{#3}
}


\begin{document}

\recn{6}{3/13}{March 13, 1998}



\begin{problems}

\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


\problem

\textbf{Life and Death.}
In ancient Mars, cannibalism was an essential way of life. 
The Marons and the Batons
were two species that lived for several thousand years in 
close contact.
Every year, first all the Marons sustained themselves by first
consuming Batons: two Marons ate one Baton between them.
Then they reproduced: one-year-old Marons 
doubled in number
while Marons that were two or older tripled in number.
Then the surviving Batons consumed one Maron each
and then all the Batons reproduced to quadruple in number. This cycle
repeated every year. After 1 year there were two 1-year old Marons and
two 1-year old Batons. After 2 years there were two 1-year olds and
two 2-year olds in each of the two species.  How many of each 
will there be of each species at the end of $n$ years?


\end{problems}
\end{document}
