\documentclass[12pt,twoside]{article}   
\usepackage{light}

%\hidesolutions
\showsolutions

\begin{document}

\problemset{7}{October 19, 2004}{\textit{Monday October 25 at 9 PM}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[10 points]
Less well-known than the Towers of Hanoi--- but no less fascinating---
are Towers of Sheboygan, WI.  As in Hanoi, the puzzle in Sheboygan
involves 3 posts and $n$ disks of different sizes.  Initially, all the
disks are on post \#1:

\begin{center}
\unitlength=0.6pt
\begin{picture}(600,190)(0,-30)
% \put(0,-30){\dashbox(600,190){}} % bounding box

\put(99,0){\dashbox(2,140){}}
\put(99,140){\framebox(2,20){}}
\put(30,0){\framebox(140,20){}}
\put(40,20){\framebox(120,20){}}
\put(50,40){\framebox(100,20){}}
\put(60,60){\framebox(80,20){}}
\put(70,80){\framebox(60,20){}}
\put(80,100){\framebox(40,20){}}
\put(90,120){\framebox(20,20){}}
\put(299,0){\framebox(2,160){}}
\put(499,0){\framebox(2,160){}}
\put(0,-5){\framebox(600,5){}}
\put(100,-20){\makebox(0,0){Post \#1}}
\put(300,-20){\makebox(0,0){Post \#2}}
\put(500,-20){\makebox(0,0){Post \#3}}
\end{picture}
\end{center}

The objective is to transfer all $n$ disks to post \#2 via a sequence
of moves.  A move consists of removing the top disk from one post and
dropping it onto another post with the restriction that a larger disk
can never lie above a smaller disk.  Furthermore, a local ordinance
requires that \textit{a disk can be moved only from post \#1 to post
\#2, from \#2 to \#3, or from \#3 to \#1.}  Thus, for example, moving
a disk directly from post \#1 to post \#3 is not permitted.
\end{problem}

\bparts

\ppart Briefly describe a solution to the Towers of Sheboygan puzzle.

\solution{Use a recursive procedure: to move an initial stack of $n$
blocks to the next post, move the top stack of $n-1$ disks to the furthest
post by moving it to the next post two times, then move the big, $n$th
disk to the next post, and finally move the top stack another two times to
land on top of the big disk.

This procedure leads to a simple linear recurrence, and gets full credit
as an answer.  But it turns out not to be the most efficient procedure for
moving the stack.

Namely, a better (indeed optimal, but we won't prove this) procedure can
be defined in terms of two mutually recursive procedures, procedure
$P_1(n)$ for moving a stack of $n$ disks 1 pole forward, and $P_2(n)$
for moving a stack of $n$ disks 2 poles forward.  It's obvious how to do
this for $n=1$.  For $n>1$, define:

$P_1(n)$: Apply $P_2(n-1)$ to move the top $n-1$ disks two poles forward
to the third pole.  Then move the remaining big disk once to land on
the second pole.  Then apply $P_2(n-1)$ again to move the stack of $n-1$
disks two poles forward from the third pole to land on top of the big
disk.

$P_2(n)$: Apply $P_2(n-1)$ to move the top $n-1$ disks two poles forward
to land on the third pole.  Then move the remaining big disk to the second
pole.  Then apply $P_1(n-1)$ to move the stack of $n-1$ disks one pole
forward to land on the first pole.  Now move the big disk 1 pole forward
again to land on the third pole.  Finally, apply $P_2(n-1)$ again to move
the stack of $n-1$ disks two poles forward to land on the big disk.}

\ppart Let $S_n$ be the number of moves needed to solve the $n$-disk
problem.  Express $S_n$ with a recurrence equation and sufficient base
cases.

\solution{
For the first procedure, we have
\begin{align}
S_1 & = 1,\notag\\
S_n & = 2S_{n-1} + 1 + 2S_{n-1} = 4S_{n-1} + 1 & \text{for }n > 1\label{4S}.
\end{align}

For the second procedure, in addition to the number, $S_n$, of steps to
move a stack of $n$ disks one pole forward a stack of $n$, let 
$T_n$ be the number of steps to move a stack of $n$ disks two poles
forward.  From the definitions of procedures $P_1$ and $P_2$ we have
\begin{align}
S_1 & = 1,\notag\\
T_1 & = 2,\notag\\
S_n & = T_{n-1} + 1 + T_{n-1} & \text{for } n > 1,\label{ST}\\
T_n & = T_{n-1} + 1 + S_{n-1} + 1 + T_{n-1} & \text{for } n > 1.\label{TT}
\end{align}
From these equations we first calculate that $T_2=7$.  Then,
using~\eqref{ST} to substitute for $S_{n-1}$ in~\eqref{TT}, we conclude
that for $n > 2$,
\begin{equation}\label{Trec}
T_n = 2T_{n-1} + 2 + (2T_{n-2} +1) = 2T_{n-1} + 2T_{n-2} + 3.
\end{equation}
}

\ppart Find a closed-form expression for $S_n$ by solving the
recurrence.

\solution{For recurrence~\eqref{4S}, Plug \& Chug works nicely:
\begin{align*}
S_{n} & = 4S_{n-1} + 1\\
      & = 4(4S_{n-2}+1) + 1\\
      & = 4^2 S_{n-2} + 4 + 1\\
      & = 4^2 (4S_{n-3}+1) + 4 + 1\\
      & = 4^3 S_{n-3}+ 4^2 + 4 + 1 = \dots\\
      & = 4^{n-1} S_1 + 4^{n-2} + \dots + 4^2 + 4 + 1\\
      & = 4^{n-1} + (4^{n-1}-1)/3\\
      & = \frac{4^n - 1}{3}
\end{align*}

For recurrence~\eqref{Trec}, we apply the general approach for
inhomogeneous linear recurrences: the characteristic polynomial is $x^2 -
2x - 2 $ with roots $1 \pm \sqrt{3}$, so the general solution to the
homogenous part of~\eqref{Trec} is
\[
A(1 + \sqrt{3})^n + B(1 - \sqrt{3})^n.
\]

Since the inhomogeneous term of~\eqref{Trec} is constant, we guess that a
particular solution will be some constant, $c$.  This requires that $c =
2c + 2c + 3$, namely, $c=-1$.  So the most general solution
to~\eqref{Trec} is of the form
\begin{equation}\label{AB}
A(1 + \sqrt{3})^n + B(1 - \sqrt{3})^n - 1.
\end{equation}
Now we use the boundary conditions $T_1 =2, T_2 = 7$ and~\eqref{AB} to
obtain linear equations in $A$ and $B$:
\begin{align*}
A(1 + \sqrt{3}) + B(1 - \sqrt{3}) - 1 & = 2\\
A(1 + \sqrt{3})^2 + B(1 - \sqrt{3})^2 - 1 & = 7.
\end{align*}


Solving these equations, we find $A = (3+2\sqrt{3})/6$ and $B =
(3-2\sqrt{3})/6$, so
\[
T_n = \frac{3+2\sqrt{3}}{6} (1 + \sqrt{3})^n + \frac{3-2\sqrt{3}}{6} (1 - \sqrt{3})^n
      -1.
\]
Now using~\eqref{ST}, we conclude that
\[
S_n = \frac{3+2\sqrt{3}}{3}(1 + \sqrt{3})^{n-1} + \frac{3-2\sqrt{3}}{3}(1 - \sqrt{3})^{n-1} - 1.
\]
In particular, we conclude that $S_n = \Theta((1+ \sqrt{3})^n) = o(4^n)$,
so the second procedure for moving a stack of $n$ disks is vastly more
efficient thah the first one.}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[10 points] The following recurrence was invented by a
late Italian renaissance scholar named Giardi Invertabinacci, who
earned a certain repute in his age for mocking profound ideas, poetry,
sculpture, and even architecture by constructing upside-down or
backward replicas of the original.  His scaled model of the famed
Tower of Pisa still stands-- upside down, but not leaning-- outside
Palermo.  His one venture into mathematics was this recurrence
relation, recorded in a letter to a contemporary mathematician and
reproduced below in modern notation.\footnote{Yeah, yeah, me made all
this up.  But good story, eh?}
%
\begin{align*}
x_1 & = 1 \\
x_2 & = 1 \\
x_{n+1} & = \frac{x_{n} x_{n-1}}{x_{n} + x_{n-1}}
\end{align*}

\bparts

\ppart Guess the solution to the recurrence.  Your solution
may be expressed in terms of Fibonacci numbers.

\solution{
We compute the first few terms to form the basis for a guess at the
general solution.

\begin{eqnarray*}
x_1	& = &	1 \\
x_2	& = &	1 \\
x_3	& = &	\frac{x_2 x_1}{x_2 + x_1}
	= 	\frac{1 \cdot  1}{1 + 1}
	= 	\frac{1}{2} \\
x_4	& = & 	\frac{x_3 x_2}{x_3 + x_2}
	= 	\frac{\frac{1}{2} \cdot  1}{\frac{1}{2} + 1}
	= 	\frac{1}{3} \\
x_5	& = &	\frac{x_4 x_3}{x_4 + x_3}
	= 	\frac{\frac{1}{3} \cdot \frac{1}{2}}
			{\frac{1}{3} + \frac{1}{2}}
	= 	\frac{1}{5} \\
x_5	& = & 	\frac{x_5 x_4}{x_5 + x_4}
	= 	\frac{\frac{1}{5} \cdot \frac{1}{3}}
			{\frac{1}{5} + \frac{1}{3}}
	= 	\frac{1}{8}
\end{eqnarray*}

\medskip
{\bf Guess.} The solution to the recurrence is $x_n = 1 / F_n$.
\medskip
}

\ppart Use strong induction to prove your guess correct.

\solution{
\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition that $x_n =
1 / F_n$.  In the base cases, $P(1)$ is true because $x_1 = 1 = 1 /
F_1$, and $P(2)$ is true because $x_2 = 1 = 1 / F_2$.  In the
inductive step, for $n \geq 2$ assume $P(1), \ldots, P(n)$ to prove
$P(n+1)$.  We reason as follows:
\begin{align*}
x_{n+1} & = 	\frac{x_{n} x_{n-1}}{x_{n} + x_{n-1}} & \text{(def. of $x_{n+1}$)}\\
	& = 	\frac{(1/F_n)(1/F_{n-1})}{1/F_n + 1/F_{n-1}} & \text{(ind. hyp.)}\\
	& = 	\frac{1}{F_{n-1} + F_{n}} & \text{(simplification)}\\
	& = 	\frac{1}{F_{n+1}} & \text{(Fibonacci recurrence)}
\end{align*}

\iffalse
The second step uses the induction hypotheses, the third step is
simplification, and final step uses the Fibonacci recurrence.
\fi

\end{proof}
}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}[20 points]
A seasoned MIT undergraduate can:

\begin{itemize}
\item Complete a problem set in 2 days.
\item Write a paper in 2 days.
\item Take a 2-day road trip.
\item Study for an exam in 1 day.
\item Play foosball for an entire day.
\end{itemize}

An \textit{$n$-day schedule} is a sequence of activities that require a
total of $n$ days.  For example, here are three possible 7-day schedules:

\begin{center}
\begin{tabular}{l}
pset, paper, pset, foosball \\
paper, study, foosball, pset, study \\
road trip, road trip, road trip, study
\end{tabular}
\end{center}

\bparts

\ppart Express the number of possible $n$-day schedules using a
recurrence equation and sufficient base cases.

\solution{
\begin{align*}
S(0) & = 1,\\
S(1) & = 2.
\end{align*}
Any schedule for $n>1$ days ends with one of 3 possible 2-day activities
or one of 2 possible 1-day activities.  So
\begin{align*}
S(n) & = 2S(n-1) + 3S(n-2) & \text{for $n>1$.}
\end{align*}
}

\ppart Find a closed-form expression for the number of possible
$n$-day schedules by solving the recurrence.

\solution{The characteristic polynomial for this linear homogeneous
recurrence is $x^2-2x-3 = (x+1)(x-3)$.  Hence the solution is of the form
$S(n) = a(-1)^n + b3^n$.  Letting $n=0$, we conclude that $a+b = 1$, and
letting $n=1$, we conclude $-a+3b =2$, so $b=3/4$, $a=1/4$, and
\[
S(n) = \frac{3^{n+1} + (-1)^{n}}{4}.
\]
}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[15 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 values of $a$ is $A'$ asymptotically
faster than $A$?
\end{problem}

\solution{Using the Akra-Bazzi 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 = (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
$(1/2) \log_2 a < \log_2 7$, or that $a < 7^2$.
Hence, $a < 49$.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[20 points]
Find closed-form solutions to the following linear recurrences.

\bparts

\ppart $x_{n} = 5 x_{n-1} - 8 x_{n-2} + 4 x_{n-3} \quad
	(x_0 = 1, x_1 = 2, x_2 = 3)$

Hint: 1 is a root.

\solution{ The characteristic equation is $r^3 - 5 r^2 + 8 r - 4 = 0$.
Solving a cubic equation can be messy process, but in this case the
roots are easy to find:
\begin{align*}
r_1 & =  2 \\
r_2 & =  2 \\
r_3 & =  1
\end{align*}

Therefore a general form for a solution is
\[
x_n  = A 2^n + B n 2^n + C.
\]

Substituting the initial conditions into this general form gives a
system of linear equations.
\begin{eqnarray*}
1 & = & A + C \\
2 & = & 2 A + 2 B + C \\
3 & = & 4 A + 8 B + C
\end{eqnarray*}

The solution to this linear system is $A = 2$, $B = -1/2$, and
$C = -1$.  The complete solution to the recurrence is therefore
\[
x_n  =  2^{n+1} - n 2^{n-1} - 1.
\]
}

\ppart $x_{n} = 3x_{n-1} - 2 x_{n-2} + n \quad (x_0 = 0, x_1 = 1)$

\solution{
First, we find the general solution to the homogenous recurrence.  The
characteristic equation is $r^2 - 3r + 2 = 0$.  The roots of this
equation are $r_1 = 1$ and $r_2 = 2$.  Therefore, the general solution
to the homogenous recurrence is

\begin{eqnarray*}
x_n & = & A + B 2^n.
\end{eqnarray*}

Now we must find a particular solution to the recurrence, ignoring the
boundary conditions.  Since the inhomogenous term is linear, we guess
there is a linear solution, that is, a solution of the form $an + b$.  If
the solution is of this form, we must have
\[
an+b = 3(a(n-1) + b) -2(a(n-2) + b) +n,
\]
which implies the absurd conclusion that
\[
n = -(3b +a).
\]

So we make another guess, this time that there is a quadratic solution of
the form $an^2 + bn +c$.  If the solution is of this form, we must have
\[
an^2+bn+c = 3(a(n-1)^2+b(n-1)+c) - 2(a(n-2)^2+b(n-2)+c) + n,
\]
which simplifies to
\[
(2a+1)n + (b - 5a) = 0.
\]
This last equation is satisfied only if the coefficient of $n$ and the
constant term are both zero, which implies $a = -1/2$ and $b = -5/2$.
Apparently, any value of $c$ gives a valid particular solution.  For
simplicity, we choose $c = 0$ and obtain the particular solution:
\[
x_n = -\frac{1}{2}n^2 - \frac{5}{2} n.
\]

The complete solution to the recurrence is the homogenous solution
plus the particular solution:
\[
x_n = A + B 2^n -\frac{1}{2}n^2 - \frac{5}{2} n
\]
Substituting the initial conditions gives a system of linear equations:
\begin{eqnarray*}
0	& = &	A + B \\
1	& = &	A + 2 B - 3
\end{eqnarray*}

The solution to this linear system is $A = -4$ and $B = 4$.
Therefore, the complete solution to the recurrence is
\[
x_n = 2^{n+2} -\frac{1}{2}n^2 - \frac{5}{2} n - 4.
\]
}

\eparts

\end{problem}


\begin{problem}[25 points]
Find $\Theta$ bounds for the following divide-and-conquer recurrences.
Assume $T(1) = 1$ in all cases.  Show your work.

\bparts

\ppart $T(n) = 3T(\floor{n/4}) + n$

\ppart $T(n) = T(\floor{n/4}) + T(\floor{n/5}) + n$

\ppart $T(n) = 2T(\floor{n/4})+\sqrt{n}$

\ppart $T(n) = 2T(\floor{n/4}+1)+\sqrt{n}$

\ppart $T(n) = 2T(\floor{n/4+\sqrt{n}}) + 1$

\eparts

\end{problem}

\solution{
\begin{enumerate}
\item[]
\begin{enumerate}

\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/5$, $h_1(n) = \lfloor n/4
\rfloor - n/4$, $h_2(n) = \lfloor n/5 \rfloor - n/5$, $g(n) = n$, $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 = 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}).
\]

\end{enumerate}

\end{enumerate}
}

\end{document}                            
