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

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{7}{October 22, 1996}{Start of Class, Tuesday, October 29}

{\bf Reading:} Sections 5.1--5.3 of {\it Discrete Mathematics and its 
Applications} by Kenneth H. Rosen, and {\it Notes on Better Master Theorems}
by Tom Leighton.

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%problem 
{\bf [15 points]}

Do exercise $5.1-16$ of Rosen.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%problem 4.3-2 of clr
{\bf [10 points]}

The running time of an algorithm $A$ is described by the recurrence 
$T(n)=7T(n/2)+n^2$. A competing algorithm $A'$  has a running time of
$T'(n)=aT'(n/4)+n^2$. What is the largest integer value for $a$ such that
$A'$ is asymptotically faster than $A$?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf [20 points]}

Use the formula given in class to find tight asymptotic bounds ($\Theta$) 
for the following divide-and-conquer recurrences. 
For each recurrence, $T(1)=1$ and $T(n)=\Theta(1)$ for all constant $n$.
State the value of $p$ you get for each recurrence (which can be left
in the form of logs). Also, state the values of the $a_i, b_i,~ \mbox{and}~
h_i(n)$ for each recurrence.
\bparts
\ppart $T(n) = 3T\left(\floor{n\over 3}\right) + n$.
\ppart $T(n) = 4T\left(\floor{n\over 3}\right) + n^2$.
\ppart $T(n) = 3T\left(\floor{n\over 4}\right) + n$.
\ppart $T(n)=T\left(\floor{n\over 4}\right)+T\left(\floor{n\over 3}\right)+n$.
\ppart $T(n)=T\left(\ceil{n\over 4}\right)+T\left(\floor{{3n}\over 4}\right)+n$.
\ppart $T(n) = 2T(n/4)+\sqrt{n}$.
\ppart $T(n) = 2T(n/4+1)+\sqrt{n}$.
\ppart $T(n) = 2T(n/4+\sqrt{n}) + 1$.
\ppart $T(n) = 3T(n^{1/3})+\log_3{n}$.  %ps1, 6.046
\ppart $T(n) = \sqrt{e}T(n^{1/e})+\ln{n}$.    
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf [10 points]}

Give asymptotic upper and lower bounds for $T(n)$ in each of the following 
recurrences. Assume
that $T(n)$ is constant for $n\leq 2$. Make your bounds as tight as
possible, and justify your answers.

\bparts
\ppart $T(n) = T(\sqrt{n})+1$.          %4-1-h,clr (page 72)
\ppart $T(n) = \sqrt{n}T(\sqrt{n})+n$.  %4-4-f,clr (page 73)
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf [10 points]}

Find an exact closed form solution for the recurrence
$$T(n) = \sum_{i=1}^{n-1} iT(i)$$ for $n>1$ and $T(1)=1$.
(\hint  Find a simple formula for $T(n)-T(n-1)$.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf [15 points]}

Find an exact closed form solution for the recurrence
$$T(n) = 4T(n-1) - 4T(n-2) + n^2$$ 
for $n>1$, and $T(0)=0$, $T(1)=1$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf [20 points]}

{\bf The graduate-student job problem made worse.} 
Consider the following depressing scenario: 
Every year, each professor of computer science graduates one new graduate
student who holds a postdoc for one year and then goes on to become a 
professor the following year.
To compound the miseries of newly graduating students, in year $n\geq 2$,
there are $2^{n-2}$ physicists who change careers to become computer science 
professors without going to graduate school. 
Let $f(n)$ denote the number of computer science professors after $n$ years.
Assume $f(0)=0$ and $f(1)=1$.  It follows that $f(2)=2$: in year 2,
there are two CS professors, namely the one CS professor from year 1 and the 
one physicist transfer (there is also one postdoc who graduated in year 1 
and will be professor in year~3).

\bparts
\ppart
Compute $f(3)$, $f(4)$, and $f(5)$.
\ppart
Set up a recurrence relation obeyed by~$f(n)$.
\ppart
Solve your recurrence to find a closed form for~$f(n)$.
\eparts


\end{problems}

\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






