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

\input{macros-course}

\begin{document}

\tutprobn{6}{3/12/99}{March 12, 1999 (revised 8pm)}

\section*{Team Problems}

\begin{problems}

\problem \textbf{Fast Medians.} The \emph{median} among $n$ ordered
elements is a ``middle'' element when they are sorted; it's unique if $n$
is odd and there are two medians if $n$ is even.  We've seen above that
merge-sorting $n$ elements takes $O(n \log n)$ comparisons.  Next week
we'll even show that sorting by any method whatsoever takes $\Omega(n \log
n)$ comparisons.  So according to the definition, it seems that $\Omega(n
\log n)$ comparisons would be needed to find the median among $n$
elements.  This was pretty much taken for granted until the 1970's when
Manuel Blum (a Professor at Berkeley a few years past his MIT Ph.D.)
discovered an astonishing, ingenious algorithm to find the median among
$n$ elements.

Blum begins by doing $\Theta(n)$ comparisons to select a certain subset of
$n/5$ elements, then recursively finding the median of these $n/5$.  This
initial median is then compared to \emph{all} the elements in a way which
determines a subset of at most $7n/10$ elements.  Blum then shows that
finding the true median is no more difficult than finding the median of
this last subset of $7n/10$ elements.

Let $M(n)$ be the number of comparisons needed by Blum's procedure.  The
description above is enough to obtain a recurrence equation for $M$.
State the recurrence and then derive a $\Theta()$ bound on $M$.


\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
newborn Maron each, and then all the Batons reproduced to quadruple in
\iffalse
correction 3/12/99 8pm: insert ``newborn'' above
\fi
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?  Try for an
exact closed form answer rather than just a $\Theta()$ bound.

\end{problems}

\end{document}
