\documentstyle[12pt,epic,eepic,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{6}{October 17, 1997}

\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$?

\bigskip

Using the Akra-Bazzi generalization of the master theorem, we have
that for $T$, $k=1, a_1 = 7, b_1 =1/2, g(n) = n^2$ and for $T'$,
$k=1, a_1 = a, b_1 =1/4, g(n) = n^2$.  In both cases, $g'(n) = 2n$
which is polynomially bounded.  In the first case (for $T$), we have that
$7\cdot(1/2)^p = 1$ or that $p = \log_2 7$.  In the second case (for
$T'$), we have that $a \cdot (1/4)^p = 1 \Rightarrow a \cdot (1/2)^{2p}
= 1 \Rightarrow p = \frac{1}{2} \log_2 a$.  
This gives

$$
T(n) = \Theta(n^{\log_2 7} (1+ \int_1^n \frac{u^2}{u^{\log_2 7 + 1}} du)) =
\Theta(n^{\log_2 7})
$$
and 
$$
T'(n) = \Theta(n^{(\log_2 a)/2} (1+ \int_1^n \frac{u^2}{u^{(\log_2
a)/2 + 1}} du)) = \Theta(n^{(\log_2 a)/2} (1 + \int_1^n u^{1- (\log_2
a)/2} du)),
$$
so that if $(\log_2 a)/2 > 2$, we have that $T'(n) = \Theta(n^{(\log_2
a)/2})$ and if $(\log_2 a)/2 = 2$, we have that $T'(n) = \Theta(n^{(\log_2
a)/2} \log n) = \Theta(n^2 \log n)$ and if $(\log_2 a)/2 < 2$, we have that $T'(n) = \Theta(n^2)$.  

This means that for $A'$ to be asymptotically faster than $A$, we need to have
$\frac{1}{2} \log_2 a < \log_2 7$, or that $a < 7^2$.
Hence, $a < 49$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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.

\bigskip

\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}

\bigskip

\begin{enumerate}

\item
$a_1 = 3$, $b_1 = 1/3$, $h_1(n) = \lfloor n/3 \rfloor - n/3$, $g(n) =
n$, $p = 1$,
%
$$T(n) = \Theta(n(1+ \int_1^n \frac{u}{u^2} du)) = \Theta(n \log n).$$

\item
$a_1 = 4$, $b_1 = 1/3$, $h_1(n) = \lfloor n/3 \rfloor - n/3$, $g(n) =
n^2$, $p = \log_3 4$,
%
$$T(n) = \Theta(n^{\log_3 4}(1+ \int_1^n \frac{u^2}{u^{\log_3 4 + 1}} du)) =
\Theta(n^{\log_3 4}(1+ \int_1^n u^{1 - \log_3 4} du)) = \Theta(n^2).$$

\item
$a_1 = 3$, $b_1 = 1/4$, $h_1(n) = \lfloor n/4 \rfloor - n/4$, $g(n) =
n$, $p = \frac{1}{2} \log_2 3$,
%
$$T(n) = \Theta(n^{(\log_2 3)/2}(1+ \int_1^n \frac{u}{u^{(\log_2 3)/2 +
1}} du)) = \Theta(n^{(\log_2 3)/2}(1+ \int_1^n u^{- (\log_2 3)/2} du)) 
= \Theta(n).$$

\item
$a_1 = 1$, $a_2 = 1$, $b_1 = 1/4$, $b_2 = 1/3$, $h_1(n) = \lfloor n/4
\rfloor - n/4$, $h_2(n) = \lfloor n/3 \rfloor - n/3$, $g(n) = n$, $p
= 0.5605$ (the exact value does not matter, it turns out that for this case, we only need to know that $p < 1$),
%
$$T(n) = \Theta(n^p(1+ \int_1^n \frac{u}{u^{p+1}} du)) =
\Theta(n^p(1+ \int_1^n u^{-p} du)) = \Theta(n).$$ 

\item
$a_1 = 1$, $a_2 = 1$, $b_1 = 1/4$, $b_2 = 3/4$, $h_1(n) = \lceil n/4
\rceil - n/4$, $h_2(n) = \lfloor 3n/4 \rfloor - 3n/4$, $g(n) = n$, $p
= 1$,
%
$$T(n) = \Theta(n(1+ \int_1^n \frac{u}{u^2} du)) =
\Theta(n \log n).$$

\item
$a_1 = 2$, $b_1 = 1/4$, $h_1(n) = \floor{n/4}-n/4$, 
$g(n) = \sqrt{n}$, $p = 1/2$,
%
$$T(n) = \Theta(n^{1/2}(1+ \int_1^n \frac{\sqrt{u}}{u^{3/2}} du)) =
\Theta(n^{1/2} \log n).$$

\item
$a_1 = 2$, $b_1 = 1/4$, $h_1(n) = \floor{n/4}-n/4 + 1$,
 $g(n) = \sqrt{n}$, $p = 1/2$,
%
$$T(n) = \Theta(n^{1/2}(1+ \int_1^n \frac{\sqrt{u}}{u^{3/2}} du)) =
\Theta(n^{1/2} \log n).$$

\item
$a_1 = 2$, $b_1 = 1/4$, $h_1(n) = \floor{n/4+ \sqrt{n}} - n/4$, 
$g(n) = 1$, $p = 1/2$,
%
$$T(n) = \Theta(n^{1/2}(1+ \int_1^n \frac{1}{u^{3/2}} du)) =
\Theta(n^{1/2}).$$

\item
{\bf NOTE: For this part the initial condition should have been T(2) = 1}

We can turn this recurrence into a divide and conquer recurrence with a
change of variables. First we show that $T(n)$ is non-decreasing.

\begin{claim}
For all $n \geq 3$, $T(n) \geq T(n-1)$.
\end{claim}

{\em Proof. } 
By strong induction on $n$.

I.H.:  $P(n): T(n) \geq T(n-1)$.

Base:  $n=3$: $T(3) = 3T(\ceil{3^{1/3}}) + 1 = 3T(2) + 1 = 4 > 1 = T(1)$.

Ind. Step: Assume $P(k)$ is true for all $3 \leq k \leq n$. We will prove that
$P(n+1)$ is true.  

\begin{eqnarray*}
T(n+1) & =  &3T(\ceil{{(n+1)}^{1/3}}) + \log_3 (n+1)\\
& \geq &  3T(\ceil{n}) + \log n\\
& = & T(n)
\end{eqnarray*}

So $T(n+1) \geq T(n)$. 
\qed

We will now solve the recurrence assuming $n$ is a power of $3$.
First, make the substitution $n  = 3^m$. The recurrence becomes 
$$T(3^m) = 3 T(\ceil{3^{m/3}}) + m$$.

Now define $S(m) = T(\ceil{3^m})$ for all integers $m \geq 0$. 
Note that since $T$ is non-decreasing, for all $m > 1$,  
$S(m+1) \geq S(m)$,
and hence $S$ is also a non-decreasing function.


Therefore, (remember $m$ is an integer),

\begin{eqnarray*}
S(m) & = & T(\ceil{3^m})\\
& = & T(3^m)\\
& = & 3T(\ceil{3^{m/3}}) + m\\
&\leq & 3T(3^{\ceil{m/3}}) + m\\
& \leq & 3S(\ceil{m/3}) + m
\end{eqnarray*}

That is $S(m) \leq 3S(\ceil{m/3}) + m$ 


We can then view this as $S(m) \leq 3S(m/3 + h(m)) + m$ where
$h(m) = \lceil m/3 \rceil - m/3 $. Clearly $h(m) < 1$ and hence
it is certainly $h(m) = O({ m \over (\log m)^2})$. 

Now to solve this we can apply the Akra-Bazzi theorem to

$$S(m) = 3S(\frac{m}{3}) + m,$$

for which $a_1 = 3$, $b_1 = 1/3$, $h_1(m) = 0$, $g(m) = m$, $p = 1$,

$$S(m) = \Theta(m(1+ \int_1^m \frac{u}{u^2}du)) = \Theta(m \log m),$$

so that

$$T(n) \leq T(3^{\ceil{\log n}}) = S(\ceil{\log n}) = O(\log n \log \log n).$$


Now we derive a lower bound in a similar fashion.

\begin{eqnarray*}
S(m) & = & T(\ceil{3^m})\\
&=& T(3^m)\\
&=&  3T(\ceil{3^{m/3}}) + m\\
&\geq & 3T(3^{\ceil{m/3}}) + m\\
&\geq & 3S(\ceil{m/3}) + m
\end{eqnarray*}

That is $S(m) \geq 3S(\ceil{m/3}) + m$.

Define a new recurrence $S'(m) = 3S'(\ceil{m/3}) + m$ with
$S'(0) = 1$.

\begin{claim}
$S(m) \geq S'(m)$
\end{claim}

{\em Proof. } 
By strong Induction on $m$.

I.H. : $P(m) : S(m) \geq S'(m)$.

Base : $m=1$: $S(0) = S'(0) = 1$.

Ind. Step: Assume $P(k)$ is true for all $k \leq m$.
We will prove $P(m+1)$. 

\begin{eqnarray*}
S(m) &\geq& 3S(\ceil{m/3}) + m\\
&\geq& 3S'(\ceil{m/3}) + m\\
&\geq &S'(m)
\end{eqnarray*}

\qed

Now we can apply Akra-Bazzi to solve the recurrence for
$S'$ in a similar way as for the upper bound to get 
$S'(m) = \Theta(m \log m)$.
From the claim above this implies that $S(m) = \Omega(m \log m)$.

Hence $T(n) =  \Omega (\log n \log \log n)$.
From the upper and lower bounds we conclude that 
$T(n) = \Theta( \log n \log \log n)$.

\item

This problem is similar to that of part 9.
We make the substitution $n = e^m$ and 
set $S(m) = T(e^m)$.  Then the recurrence becomes

$$S(m) = \sqrt{e} S(\frac{m}{e}) + m,$$

for which $a_1 = \sqrt{e}$, $b_1 = 1/e$, $h_1(m) = 0$, $g(m) = m$, $p = 1/2$,

We follow the steps in part 9 to conclude that,

$$S(m) = \Theta(m^{1/2}(1+ \int_1^m \frac{u}{u^{3/2}}du)) = \Theta(m),$$

so that

$$T(n) = S(\log n) = \Theta(\log 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)$.)

\bigskip

\begin{eqnarray*}
T(n)-(n-1)T(n-1) & = &  \sum_{i=1}^{n-2}{iT(i)} = T(n-1)~ \Rightarrow\\
T(n) & = & (n-1)T(n-1)+T(n-1) \Rightarrow\\
T(n) & = & nT(n-1)
\end{eqnarray*}

$T(1)=1, ~T(2)=1\cdot T(1)=1,~\mbox{and}~~T(3)=2\cdot T(2)+1\cdot T(1)=3$.  
So we have:
\[
T(n) = \left\{ \begin{array}{ll}
       1   & \mbox{for $n=1$}\\
      n!/2 & \mbox{for $n\geq 2$}
                \end{array}
        \right. 
\]
Verify by induction:

{\bf Base case:} $n=2$

$T(2)=\sum_{i=1}^1{iT(i)}=1\cdot T(1)=1=2!/2$.

{\bf Inductive step:}
 
\begin{eqnarray*}
T(n+1) &=& (n+1)T(n)\\
       &=& (n+1)~n!/2 ~~~~~\mbox{by the induction hypothesis}\\
       &=& (n+1)!/2
\end{eqnarray*}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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$.

\bigskip

First we find the general solution of the homogeneous recurrence:

$T(n)=4T(n-1)-4T(n-2)$. 

Its characteristic equation is:
$\alpha^2-4\alpha+4=0 \Longrightarrow (\alpha-2)^2=0$.
So $2$ is a root of multiplicity $2$.  
The general solution has the form  $A2^n+Bn2^n$ for $A, B\in \reals$. 

Now we find a particular solution to the non-homogeneous recurrence (ignoring
initial conditions). For a polynomial ``drive'', we try a polynomial of 
the same degree (higher if $1$ is a root of characteristic equation).
Guess $T(n)=an^2+bn+c$, and solve for $a,b$, and $c$ satisfying 
the recurrence:

\begin{eqnarray*}
an^2+bn+c &=& 4(a(n-1)^2 + b(n-1) + c)-4(a(n-2)^2 + b(n-2) + c)+n^2\\
          &=& 4((n-1)^2 - (n-2)^2)+4b((n-1)- (n-2))+4c(1-1) + n^2\\
          &=& 4a(2n-3) + 4b + n^2 \\
          &=& n^2 + 8an + 4b - 12c
\end{eqnarray*}
which implies that $a=1,~ b=8a=8,~ c=4b-12a=32-12=20$.

So a general solution to the inhomogeneous recurrence is 
$A2^n+Bn2^n+n^2+8n+20$ for  $A, B\in \reals$. 

Finally we compute $A, B$ using the initial conditions:

$0=T(0)=A+20 \Rightarrow A=-20$.

$1=T(1)=2A+2B+1+8+20=2B-40+29 \Rightarrow B=1+40-29=12 \Rightarrow B=6$.

Solution: $T(n)=(6n-20)2^n+n^2+8n+20$.

Check answers for small values of $n$ (to avoid arithmetic and algebraic
errors):

$T(0)=-20+20=0$

$T(1)=-14\cdot 2+1+8+20=-28+29=1$

$T(2)=-8\cdot 4+4+16+20=-32+40=8=4\cdot 1-4\cdot 0+2^2$.


\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 difference equation of the form \\
$f(m) = \sum_{i=1}^d a_{i}f(m-i) + g(m)$ \\

\bigskip

Let $n = 2^m$.

$T(2^m) = \sum_{i=1}^d a_{i}T(2^m/2^i) + G(2^m) =
\sum_{i=1}^d a_{i}T(2^{m-i}) + G(2^m)$

Set $f(m) = T(2^m)$ and $g(m) = G(2^m)$.


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

\bigskip

Applying the transformation in (b), we obtain the recurrence

$f(m) = 3f(m-1) - 2f(m-2) + 3^m$.

The homogeneous part of this recurrence has characteristic equation

$x^2 - 3x + 2$

The roots are $2$ and $1$, so a solution has the form
$c_1 (1)^m + c_2 2^m = c_1 +c_2 2^m$.

To obtain a particular solution we try $k 3^m$ to obtain:

$k (3^2) - 3k(3) + 2k = 3^2 \rightarrow k = 9/2$.

So the general solution to the linear recurrence is:

$f(m) = c_1 + c_2 2^m + (9/2) 3^m$

Transforming back to the original form for $n= \log_2 m$ we obtain

$T(n) = c_1 + c_2 n + (9/2) 3^{log_2 n}$

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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(n)$ denote the number of outlaws caught in year $n$.
Write a recurrence relation for $f(n)$ and obtain a closed-form
solution.  Do you ever get a fractional outlaw?

\bigskip

\[f(n) = {1 \over 2}(f(n-1) + f(n-2))\]
This is a homogeneous linear recurrence. We solve the characteristic
equation, $2x^2 -x - 1 = 0$, to get the roots $1$ and $-1/2$. Hence
the general solution is of the form $f(n) = A + B(-1/2)^n$. Using the
initial conditions $f(0) = 100$ and $f(1) = 300$ we find that the
general solution is 

$f(n) = 700/3 - (400/3)(-1/2)^n$.

The first fractional number of outlaws is obtained when $n=3$.

\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$.

\bigskip

Let $g(n)$ denote the number of outlaws caught in year $n$ under
this model.  Again, write a recurrence relation for $g(n)$ and 
obtain a closed-form solution.

\[g(n) = {1 \over 3}(g(n-1) + g(n-2) + g(n-3))\]
This is a homogeneous linear recurrence. We solve the characteristic
equation, $3x^3 -x^2 - x - 1 = 0 \Rightarrow
(x-1)(3x^2+2x+1) = 0$, to get the roots $1$,
$\frac{-1-i\sqrt{2}}{3}$ and $\frac{-1+i\sqrt{2}}{3}$ where
$i = \sqrt{-1}$ denotes the imaginary unit. 
Hence the general solution is of the form
 
$g(n) = A +B(\frac{-1-i\sqrt{2}}{3})^n + C(\frac{-1+i\sqrt{2}}{3})^n$.
 
Using the initial conditions $g(0) = 100$, $g(1) = 300$ and $g(2) = 200$ we
find that the general solution is 

$$
g(n) = {650 \over 3} +
{-25 \over 3}(7-i4\sqrt{2}) \left(\frac{-1-i\sqrt{2}}{3} \right)^n +
{-25 \over 3}(7+i4\sqrt{2}) \left(\frac{-1+i\sqrt{2}}{3} \right)^n
$$

\eparts

\end{problems}
\end{document}

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