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

\begin{document}

\pset{6}{October 7, 1997}{October 14, 1997}

{\bf Reading assignment: 5.1-5.3 in Rosen }

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 1
\problem {\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$. 
For what value of  $a$ is $A'$ asymptotically faster than $A$?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
\problem{\bf [30 points]}

Use the formula given in class (Akra-Bazzi)
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.

\begin{enumerate}
\item $T(n) = 3T\left(\floor{n\over 3}\right) + n$.
\item $T(n) = 4T\left(\floor{n\over 3}\right) + n^2$.
\item $T(n) = 3T\left(\floor{n\over 4}\right) + n$.
\item $T(n)=T\left(\floor{n\over 4}\right)+T\left(\floor{n\over 3}\right)+n$.
\item $T(n)=T\left(\ceil{n\over 4}\right)+T\left(\floor{{3n}\over 4}\right)+n$.
\item $T(n) = 2T(\floor{n/4})+\sqrt{n}$.
\item $T(n) = 2T(\floor{n/4}+1)+\sqrt{n}$.
\item $T(n) = 2T(\floor{n/4+\sqrt{n}}) + 1$.
\item $T(n) = 3T(\ceil{n^{1/3}})+\log_3{n}$.  
\item $T(n) = \sqrt{e}T(\floor{n^{1/e}})+\ln{n}$.    
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
\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 4
\problem {\bf [30 points]}

Find an exact closed form solution for the following recurrences.

\bparts

\ppart 
$$T(n) = 4T(n-1) - 4T(n-2) + n^2$$ 
for $n>1$, and $T(0)=0$, $T(1)=1$.

\ppart
Consider the recurrence \\
$T(n) = \sum_{i=1}^d a_{i}T(n/2^i) + G(n)$

Find a transformation $n \rightarrow m$ that will convert this problem in
a linear recurrence of the form \\
$f(m) = \sum_{i=1}^d a_{i}f(m-i) + g(m)$ \\

\ppart 
Apply your results from part (b),
to find the exact solution of the recurrence relation \\
$T(n) = 3T(n/2) - 2T(n/4) + 3^{\log_2 n}$

\eparts

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

Bounty hunters in the Old West used the following empirical model:
the number of outlaws caught (dead or alive)
in a given year is the average of the
number caught in the previous two years.  
Let's try out this model in the following hypothetical situation --- 
in year $0$, there were $100$ outlaws
caught, and in year $1$, there were $300$ outlaws caught. 

({\em note that this model allows fractional outlaws})

\bparts
\ppart
Let $f(i)$ denote the number of outlaws caught in year $i$.
Write a recurrence relation for $f(i)$ and obtain a closed-form
solution.  Do you ever get a fractional outlaw?


\ppart
Now let's consider the following variation on this model: the number
of outlaws caught in a given year is the average of the number
caught in the previous {\em three} years.  To start things off,
suppose that $100$ were caught in year $0$, $300$ in year $1$, and
$200$ in year $2$.

\eparts

\end{problems}
\end{document}

% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
