\documentstyle[12pt,twoside,macpsfig]{article}
\input{macros-course}

\begin{document}

\handout{ps5}{Problem Set 5}{March 1, 1994}

\pset{5}
{\bf Reading:\ } Maurer \& Ralston: Chapter 5, Chapter 4 of CLR
(handout 20).

\medskip

The problems are divided into oral problems (prefix~``{\bf O}'') and
written problems (prefix~``{\bf W}'').  Both the oral and written
problems are due in tutorial on Monday, March 7.  There is no lecture
on March 8.  Remember to write up each problem on a separate page or
pages, with your name on each sheet.

\medskip


\medskip

\begin{problems}


\oproblem
Consider the following recurrence:
\[T(n) = \left\{ \begin{array}{ll}
		    \Theta(1) & \mbox{for $n = 1$}\\
		    aT(\frac{n}{2}) + n^2 & \mbox{for $n > 1$}
		 \end{array}
	 \right. \]
Solve it for 
\begin{problemparts}
\problempart
 $a = 3.99$
\problempart $a = 4$
\problempart $a = 4.01$
\end{problemparts}

\oproblem
Solve the following recurrence:
\[T(n) = \left\{ \begin{array}{ll}
		    \Theta(1) & \mbox{for $n = 1$}\\
		    2T(\frac{n}{4}) + T(\frac{n}{2}) + n & \mbox{for $n > 1$}
		 \end{array}
	 \right. \]

\oproblem
Get asymptotically tight upper and lower bounds for the following recurrence:
\[T(n) = \left\{ \begin{array}{ll}
		    \Theta(1) & \mbox{for $n = 1$}\\
		    T(\frac{n}{2}+17) + T(\frac{n}{2}-5)+\Theta(n) & \mbox{for $n > 1$}
		 \end{array}
	 \right. \]


\oproblem
Solve the following recurrence (Hint: consider change of recurrence):
\[T(n) = \left\{ \begin{array}{ll}
		    \Theta(1) & \mbox{for $n = 1$}\\
		    nT(\frac{n}{2}) & \mbox{for $n > 1$}
		 \end{array}
	 \right. \]

\oproblem
Solve the following recurrence (Hint: simplify and substitute):
\[T(n) = \left\{ \begin{array}{ll}
		    \Theta(1) & \mbox{for $n = 1$}\\
		    nT(\frac{n}{2}) + n& \mbox{for $n > 1$}
		 \end{array}
	 \right. \]

\oproblem
Here is a recurrence that was once given in a 6.046 exam. Not only was
no student able to do this problem, even the professor could not solve
it. Try and give as tight a solution as you can:
\[T(n) = \left\{ \begin{array}{ll}
		    \Theta(1) & \mbox{for $n = 1$}\\
		    T(n-1)+T(\frac{n}{2})& \mbox{for $n > 1$}
		 \end{array}
	 \right. \]

\oproblem
You have a computer which can do infinite precision arithmetic, i.e.
it can multiply two irrational numbers exactly in one time step.
Describe an $O(\log n)$ step algorithm on this computer to compute
$F_n$, the $n$th Fibonacci number. (Hint: first figure out how to
compute $X^n$ in $O(\log n)$ steps for any $X$.)

\oproblem
An idealised {\em birth-death model} for bacteria. Each individual of a
certain species of bacteria lives for two years. Each year each
(alive) bacterium spawns off two copies of itself (making for a total
of three).

\begin{problemparts}
\problempart
Let $NB_n$ and $OB_n$ denote the number of new-born and one-year old
bacteria, respectively, at the end of year $n$. Set up recurrence
relations for $NB_{n+1}$ and $OB_{n+1}$ in terms of $NB_n$ and $OB_n$.

\problempart
Let $P_n$ denote the number of bacteria alive at the end of year $n$.
Set up a recurrence for $P_n$ and solve it. Given that the species
consists of one new-born bacterium at time 0, find the size of the
population at the end of year $15$.

\end{problemparts}

\newpage

\wproblem
\begin{problemparts}
\problempart
Solve the following recurrence (Hint: consider change of variables):
\[T(n) = \left\{ \begin{array}{ll}
		    \Theta(1) & \mbox{for $n = 1$}\\
		    \sqrt{n}T(\sqrt{n}) + n & \mbox{for $n > 1$}
		 \end{array}
	 \right. \]

\problempart
Consider the following recurrence:
\[T(n) = \left\{ \begin{array}{ll}
		    \Theta(1) & \mbox{for $n = 1$}\\
		    aT(\frac{n}{2}) + 1 & \mbox{for $n > 1$}
		 \end{array}
	 \right. \]
Solve it for 
 $a = .99$,  $a = 1$ and  $a = 1.01$.
\end{problemparts}


\wproblem
You have $n$ identical looking coins. All you know for sure is that
more than half of them are made of gold. The rest of them are made of
(possibly different) base metals. You have access to a machine which,
given two coins, will tell you whether they are made of the same metal
or whether they are made of different metals. But each query to the
machine costs money. Devise an algorithm which determines all the gold
coins in a linear (in $n$) number of queries. (Hint: make use of the
recurrence relation $T(n) = T(\frac{n}{2}) + \frac{n}{2}$.)

\wproblem
The {\em graduate-student job problem} (made worse). Consider the following
(depressing) scenario: Each year every professor spawns one new
student who, after being a postdoc for one year goes on to become a
professor the following year.

\begin{problemparts}
\problempart
Set up a recurrence relation for the number of professors and solve
it. How fast does the number of professors grow? (Assume suitable
initial conditions, but nontrivial---you may not assume there are no
professors to start with)

\problempart
Now to compound the miseries of newly graduating students, in year
$n$, $g(n)$ people switch from other careers to become professors
without going to grad school. Set up the new recurrence and solve it
for $g(n) = (\frac{3}{2})^n$ and $g(n) = 2^n$.

\problempart
If $g(n) = c^n$ then for what value of $c$ will the influx of
outsiders begin to make a significant difference to the growth rate of
the number of professors (and wannabes)?
\end{problemparts}


\end{problems}


\end{document}



