\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%BEGIN Kavita's problems
% Fall 1998

%**************
%   PSET 5    *
%**************
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)}  Suppose that $n$ ovals are drawn in a plane
so that every pair of ovals intersects at either 0 or 2 points.
Let $x_n$ be the maximum number of regions that can be formed by such
a configuration of ovals.  We can express $x_n$ using the
recurrence below.

\begin{eqnarray*}
x_1 & = & 2 \\
x_{n+1} & = & x_n + 2n
\end{eqnarray*}

The region outside of any oval ``counts''; for example, one oval
defines two regions, because the oval has an inside region and an
outside region.

\begin{problemparts}

\problempart Solve this recurrence using the plug and chug method.

\solution{
First, we repeatedly apply the recurrence equation.

\begin{eqnarray*}
x_n	& = & x_{n-1} + 2(n-1) \\
	& = & x_{n-2} + 2(n-2) + 2(n-1) \\
	& = & x_{n-3} + 2(n-3) + 2(n-2) + 2(n-1)
\end{eqnarray*}

We can now guess a general form and check it by applying the
recurrence equation one more time.

\begin{eqnarray*}
x_n	& = &	x_{n-i} + 2(n-i) + \ldots + 2(n-2) + 2(n-1) \\
x_n
  & = &	x_{n-i-1} + 2(n-i-1) + 2(n-i) + \ldots + 2(n-2) + 2(n-1) \\
  & = &	x_{n-(i+1)} + 2(n-(i+1)) + 2(n-i) + \ldots + 2(n-2) + 2(n-1)
\end{eqnarray*}

Setting $i = n-1$, gives an expression for $x_n$.

\begin{eqnarray*}
x_n	& = &	x_{n-i} + 2(n-i) + \ldots + 2(n-2) + 2(n-1) \\
	& = &   x_1 + 2 + 4 + \ldots + 2(n-2) + 2(n-1) \\
	& = &   2 + 2 + 4 + \ldots + 2(n-2) + 2(n-1) \\
	& = &   2 + 2 \sum_{j=1}^{n-1} j
\end{eqnarray*}

Now we get the closed form $x_n = n(n-1) + 2$ from the formula for the
sum of an arithmetic series.
}

\problempart Describe how to arrange $n$ ovals so as to form $x_n$ regions.
No proof of correctness is required.

\solution{Make all the ovals circles of the same size.  Place the
second circle slightly right of the first, the third slightly right of
the second, and so forth.}

\end{problemparts}

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

\problem {\bf (10 points)} Consider the following recurrence.

\begin{eqnarray*}
y_0 & = & 1 \\ y_n & = & \sum_{i=1}^n y_{n-i} \cdot 2^i
\end{eqnarray*}

\begin{problemparts}

\problempart Guess the solution to the recurrence.

\solution{
First, we compute the first few terms to form the basis for a guess.

\begin{eqnarray*}
y_0	& = &	1 \\
y_1	& = &	2 \cdot y_0
	 = 	2 \cdot 1
	 = 	2 \\
y_2	& = &	2 \cdot y_1 + 4 \cdot y_0
	 = 	2 \cdot 2 + 4 \cdot 1
	 = 	8 \\
y_3	& = &	2 \cdot y_2 + 4 \cdot y_1 + 8 \cdot y_0
	 = 	2 \cdot 8 + 4 \cdot 2 + 8 \cdot 1
	 = 	32 \\
y_4	& = &	2 \cdot y_3 + 4 \cdot y_2 + 8 \cdot y_1 + 16 \cdot y_0
	 = 	2 \cdot 32 + 4 \cdot 8 + 8 \cdot 2 + 16 \cdot 1
	 = 	128 \\
\end{eqnarray*}

The above calculation suggests the following claim.

\medskip
{\bf Claim.}
The solution to the recurrence is $y_0 = 1$ and $y_n = 2^{2n-1}$ for $n
\geq 1$.
\medskip
}

\problempart Prove your guess correct using strong induction.

\solution{
\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition that
$y_0 = 1$ and $y_n = 2^{2n-1}$ for $n \geq 1$.  In the base case,
$P(0)$ holds trivially.  In the inductive step, assume $P(0), \ldots,
P(n)$ to prove $P(n+1)$.  By the definition of $y_{n+1}$, we have:

\begin{eqnarray*}
y_{n+1}	& = &	\sum_{i=1}^{n+1} y_{n+1-i} \cdot 2^i \\
	& = &	y_0 \cdot 2^{n+1} + \sum_{i=1}^n y_{n+1-i} \cdot 2^i \\
	& = &	1 \cdot 2^{n+1} + \sum_{i=1}^n 2^{2(n+1-i)-1} \cdot 2^i \\
	& = &	2^{n+1} + 2^{2n+1} \cdot \sum_{i=1}^{n} \frac{1}{2^i} \\
	& = &	2^{n+1} + 2^{2n+1} \cdot \left( 1 - \frac{1}{2^n} \right) \\
	& = &	2^{2(n+1) - 1}
\end{eqnarray*}

In the second step, we split out the special term of the summation
that contains $y_0$.  The third step uses the induction hypotheses,
and in the fourth step we pull a constant out of the summation.  The
fifth equation follows from the formula for the sum of a geometric
series.  The last step is simplication.

This shows that $P(0), \ldots, P(n)$ imply $P(n+1)$, and the claim is
proved by strong induction.
\end{proof}
}

\end{problemparts}

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

\problem {\bf (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 orignal.  His scaled model of the famed Tower
of Pisa still stands-- upside down, but not leaning-- outside Palermo.
His one venture into mathematics was a recurrence relation, recorded
in a letter to a contemporary mathematician and reproduced below in
modern notation.\footnote{Okay, your TA just made all this up.  But
good story, eh?}

\begin{eqnarray*}
x_1 & = & 1 \\
x_2 & = & 1 \\
x_{n+1} & = & \frac{x_{n} x_{n-1}}{x_{n} + x_{n-1}}
\end{eqnarray*}

\begin{problemparts}

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

\problempart Use strong induction to prove your guess correct.

\solution{
\begin{proof}
The proof is by 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)$.  From the defintion of $x_{n+1}$, we reason as follows:

\begin{eqnarray*}
x_{n+1} & = &	\frac{x_{n} x_{n-1}}{x_{n} + x_{n-1}} \\
	& = &	\frac{\frac{1}{F_n} \frac{1}{F_{n-1}}}
			{\frac{1}{F_n} + \frac{1}{F_{n-1}}} \\
	& = &	\frac{1}{F_{n-1} + F_{n}} \\
	& = &	\frac{1}{F_{n+1}}
\end{eqnarray*}

The second step uses the induction hypotheses, the third step is
simplification, and final step uses the Fibonacci recurrence.
\end{proof}
}

\end{problemparts}

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

\problem {\bf (10 points)} We have devised a new version of {\tt
MergeSort}, which we call {\tt MergeSortX19}, for the intellectually
challenged inhabitants of planet Xoros 19.

Here is how the new algorithm works.  The input is a list of $n$
distinct numbers.  If the list contains a single number, then there is
nothing to do.  If the list contains two numbers, then we sort them
with a single comparison.  If the list contains more than two numbers,
then we perform the following sequence of steps.

\begin{itemize}
\item We make a list containing the first $\frac{2}{3}n$ numbers and
sort it recursively.

\item We make a list containing the last $\frac{2}{3}n$ numbers and
sort it recursively.

\item We make a list containing the first $\frac{1}{3}n$ numbers and
the last $\frac{1}{3}n$ numbers and sort it recursively.

\item We merge the first and second lists, throwing out duplicates.

\item We merge this combined list with the third list, again throwing out
duplicates.
\end{itemize}

The final, merged list is the output.  We consider this algorithm
ideal for the slow-witted creatures of Xoros 19, because multiple
copies of each number are maintained.  Therefore, even if the sorter
occasionally forgets about a number, the algorithm can still output a
complete, sorted list.

\begin{problemparts}

\problempart Write a recurrence for the maximum number of comparisons
needed to sort a list of $n$ numbers using {\tt MergeSortX19}.  Assume
that merging a list with $l_1$ numbers and a list with $l_2$ numbers
and throwing out duplicates requires at most $2(l_1 + l_2)$
comparisons.

\solution{
\begin{eqnarray*}
T(1)	& = &	0 \\
T(2)	& = &	1 \\
T(n)	& = &	3T\left(\frac{2}{3}n\right) +
		2\left(\frac{2}{3}n + \frac{2}{3}n\right) +
		2\left(n + \frac{2}{3}n\right) \\
	& = &	3T\left(\frac{2}{3}n\right) + 6n
\end{eqnarray*}
}

\problempart Give a $\Theta$ bound on the maximum number of comparisons
used by {\tt MergeSortX19} to sort a list of $n$ numbers.

\solution{
We can apply the Akra-Bazzi method.  First, we find $p$ as shown
below.

\begin{eqnarray*}
3 \cdot \left(\frac{2}{3}\right)^p & = & 1 \\
\ln 3 - p \ln \frac{3}{2} & = & 0 \\
p & = & \frac{\ln 3}{\ln\frac{3}{2}}
\end{eqnarray*}

Now the $\Theta$ bound on the maximum number of comparisons follows
from an integration.

\begin{eqnarray*}
x_n	& = &	\Theta\left(n^p \cdot \left(1 +
		\int_1^n \frac{6u}{u^{1+p}} \ du \right)\right) \\
	& = &	\Theta\left(n^p\right) \\
	& = &	\Theta\left(n^{2.7095\ldots}\right)
\end{eqnarray*}
}
\end{problemparts}

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

\problem {\bf (15 points)}
Use the Akra-Bazzi method to find a $\Theta$ bound on the solution to
each of the following recurrences.

\begin{problemparts}

\problempart $T(n) = 4 T(\floor{\frac{n}{3}}) + n^2$

\solution{
\begin{eqnarray*}
4 \cdot (1/3)^p = 1 & \Rightarrow & p = \ln_3 4 \\
T(n)	& = &	\Theta\left(n^p \cdot \left(1 +
		\int_1^n \frac{u^2}{u^{p+1}} 
		\ du\right)\right) \\
	& = &	\Theta(n^2)
\end{eqnarray*}
}

\problempart $T(n) = T(\floor{\frac{3n}{5}}) + T(\floor{\frac{4n}{5}}) + n^2$

\solution{
\begin{eqnarray*}
(3/5)^p + (4/5)^p = 1 & \Rightarrow & p = 2 \\
T(n)	& = &	\Theta\left(n^2 \cdot \left(1 +
		\int_1^n \frac{u^2}{u^{2+1}} 
		\ du\right)\right) \\
	& = &	\Theta(n^2 \ln n)
\end{eqnarray*}
}

\problempart $T(n) = T(\floor{\frac{n}{3}}) + 2 T(\floor{\frac{n}{4}}) + n \sqrt{n}$

\solution{
\begin{eqnarray*}
(1/3)^p + 2(1/4)^p = 1 & \Rightarrow & p < 1 \\
T(n)	& = &	\Theta\left(n^p \cdot \left(1 +
		\int_1^n \frac{u^{3/2}}{u^{p+1}} 
		\ du\right)\right) \\
	& = &	\Theta\left(n^p \cdot \left(1 +
		\int_1^n u^{1/2-p}
		\ du\right)\right) \\
	& = &	\Theta(n \sqrt{n})
\end{eqnarray*}
}

\end{problemparts}

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

%**************
%   PSET 6    *
%**************
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Find closed-form solutions to the following homogenous linear
recurrences.

\begin{problemparts}
\problempart $x_{n} = 5 x_{n-1} - 6 x_{n-2} \quad (x_0 = 0, x_1 = 1)$

\solution{ The characteristic equation is $r^2 - 5 r + 6 = 0$.  The
roots can be found with the quadratic formula:

\begin{eqnarray*}
r_1 & = & 2 \\
r_2 & = & 3
\end{eqnarray*}

This implies a solution of the form

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

Substituting the initial conditions into this general form gives a
system of linear equations:

\begin{eqnarray*}
0 & = & A + B \\
1 & = & 2 A + 3 B
\end{eqnarray*}

The solution to this system is $A = -1$ and $B = 1$.  Therefore, the
final solution to the recurrence is

\begin{eqnarray*}
x_n & = & 3^n - 2^n.
\end{eqnarray*}
}

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

\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{eqnarray*}
r_1 & = & 2 \\
r_2 & = & 2 \\
r_3 & = & 1
\end{eqnarray*}

The general form of the solution is therefore

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

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 = -\frac{1}{2}$, and
$C = -1$.  The complete solution to the recurrence is therefore

\begin{eqnarray*}
x_n & = & 2^{n+1} - n 2^{n-1} - 1.
\end{eqnarray*}
}

\end{problemparts}

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

\problem Find closed-form solutions to the following inhomogenous
linear recurrences.

\begin{problemparts}

\problempart (Fibonacci Plus) $x_{n} = x_{n-1} + x_{n-2} + 1 \quad
(x_0 = 0, x_1 = 1)$

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

\begin{eqnarray*}
r_1	& = &	\frac{1 + \sqrt{5}}{2} \\
r_2	& = &	\frac{1 - \sqrt{5}}{2}
\end{eqnarray*}

Therefore, the solution to the homogenous recurrence is of the form

\begin{eqnarray*}
x_n	& = &	A \left( \frac{1 + \sqrt{5}}{2} \right)^n +
		B \left( \frac{1 - \sqrt{5}}{2} \right)^n.
\end{eqnarray*}

Next, we need a particular solution to the inhomogenous recurrence.
Since the inhomogenous term is constant, we guess a linear solution.

\begin{eqnarray*}
an + b	& = &	a(n-1) + b + a(n - 2) + b + 1 \\
	& = &	2an - 3a + 2b + 1 \\
0	& = &	an - 3a + b + 1
\end{eqnarray*}

This equation holds if we set $a = 0$ and $b = -1$.  Therefore, the
inhomogeous recurrence has the simple particular solution $x_n = -1$.
The complete solution to the recurrence is the homogenous solution
plus the particular solution:

\begin{eqnarray*}
x_n	& = &	A \left( \frac{1 + \sqrt{5}}{2} \right)^n +
		B \left( \frac{1 - \sqrt{5}}{2} \right)^n - 1
\end{eqnarray*}

All that remains is to find the constants $A$ and $B$.  Substituting
the initial conditions gives a system of linear equations.

\begin{eqnarray*}
0	& = &	A + B - 1 \\
1	& = &	A \left( \frac{1 + \sqrt{5}}{2} \right) +
		B \left( \frac{1 - \sqrt{5}}{2} \right) - 1
\end{eqnarray*}

The solution to this linear system is:

\begin{eqnarray*}
A	& = &	\frac{5 + 3 \sqrt{5}}{10} \\
B	& = &	\frac{5 - 3 \sqrt{5}}{10}
\end{eqnarray*}

Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
x_n	& = &	\left( \frac{5 + 3 \sqrt{5}}{10} \right) \cdot
			 \left( \frac{1 + \sqrt{5}}{2} \right)^n +
		\left( \frac{5 - 3 \sqrt{5}}{10} \right) \cdot
			B \left( \frac{1 - \sqrt{5}}{2} \right)^n - 1.
\end{eqnarray*}
}

\problempart $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
a solution that is quadratic:

\begin{eqnarray*}
an^2+bn+c	& = &	3(a(n-1)^2+b(n-1)+c) - 2(a(n-2)^2+b(n-2)+c) + n \\
		& = &	an^2+2an-5a+bn+b+c+n \\
0		& = &	2an - 5a + b + n
\end{eqnarray*}

This equation is solved by setting $a = -\frac{1}{2}$ and $b =
-\frac{5}{2}$.  Apparently, any value of $c$ gives a valid particular
solution; for simplicity, we choose $c = 0$.  Therefore, the
particular solution is:

\begin{eqnarray*}
x_n	& = &	-\frac{1}{2}n^2 - \frac{5}{2} n
\end{eqnarray*}

The complete solution to the recurrence is the homogenous solution
plus the particular solution:

\begin{eqnarray*}
x_n	& = &	A + B 2^n -\frac{1}{2}n^2 - \frac{5}{2} n
\end{eqnarray*}

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

\begin{eqnarray*}
x_n	& = &	2^{n+2} -\frac{1}{2}n^2 - \frac{5}{2} n - 4.
\end{eqnarray*}
}

\end{problemparts}

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

\problem The 6.042 staff recently received the following email.

\begin{verbatim}
From: grzzwk@xoros19.gammaquad.plnt
To: 6042-staff@theory.lcs.mit.edu
Subject: Pset 5 issue

Thank you for contributing the MergeSortX19 algorithm to our
``intellectually challenged'' society.  My, my-- we feel mentally
bloated by this sudden infusion of technological wizardry!

As a token of thanks, we launched a Doritofier missile on a straight
line toward Earth.  Suppose that p(t) denotes the distance between
Xoros 19 and the Doritofier after t days of flight.  At the moment of
launch, the Doritofier was here on Xoros 19, and so p(0) = 0.  After a
single day, the Doritofier had already traveled 100 units toward
Earth, so p(1) = 100.  In general, the position of the missle is given
by the following recurrence:

       p(t+1) = 1.99 * p(t) - p(t-1)

Earth happens to be 1010 units from Xoros 19.  Gotta run!  Seeya!

/Grzzwk
\end{verbatim}

\begin{problemparts}

\problempart Find a closed-form solution to the recurrence for the
distance between Xoros 19 and the Doritofier after $t$ days of flight.

\solution{ Let $c = 1.99$.  The characteristic equation of Grzzwk's
recurrence is then $r^2 - c r +1 = 0$.  The roots of this equation
are:

\begin{eqnarray*}
r_1	& = &	\frac{c + \sqrt{c^2 - 4}}{2} \\
r_2	& = &	\frac{c - \sqrt{c^2 - 4}}{2} \\
\end{eqnarray*}

Therefore, the general solution to the recurrence is:

\begin{eqnarray*}
p(t)	& = &	A \left( \frac{c + \sqrt{c^2 - 4}}{2} \right)^t +
		B \left( \frac{c - \sqrt{c^2 - 4}}{2} \right)^t
\end{eqnarray*}

Subtituting the initial conditions into this general form gives a
system of linear equations.

\begin{eqnarray*}
0	& = &	A + B \\
100	& = &	A \left( \frac{c + \sqrt{c^2 - 4}}{2} \right) +
		B \left( \frac{c - \sqrt{c^2 - 4}}{2} \right)
\end{eqnarray*}

The solution to this linear system is

\begin{eqnarray*}
A	& = &	\frac{100}{\sqrt{c^2 - 4}} \\
B	& = &	- \frac{100}{\sqrt{c^2 - 4}}
\end{eqnarray*}

Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
p(t)	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot
		\left(	\left( \frac{c + \sqrt{c^2 - 4}}{2} \right)^t -
		\left( \frac{c - \sqrt{c^2 - 4}}{2} \right)^t \right)
\end{eqnarray*}

where $c = 1.99$.  Note that $\sqrt{c^2 - 4}$ is imaginary.
}

\problempart The characteristic equation approach gives a solution to
this recurrence involving complex numbers.  This makes evalutation
awkward.  Give a closed-form solution that does not involve complex
numbers.  DeMoivre's Identity may be helpful:

\begin{eqnarray*}
(\cos \theta + i \sin \theta)^n & = & \cos n \theta + i \sin n \theta
\end{eqnarray*}

\solution{
We start with the solution obtained previously.

\begin{eqnarray*}
p(t)	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot
		\left(	\left( \frac{c + \sqrt{c^2 - 4}}{2} \right)^t -
		\left( \frac{c - \sqrt{c^2 - 4}}{2} \right)^t \right)
\end{eqnarray*}

Note that

\begin{eqnarray*}
\frac{c + \sqrt{c^2 - 4}}{2}
	& = &	\frac{c}{2} + i \cdot 
			\sqrt{1 - \left(\frac{c}{2}\right)^2} \\
	& = &	\cos \theta + i \sin \theta
\end{eqnarray*}

where $\theta = \arccos \frac{c}{2}$.  With this substitution, we can
eliminate complex numbers from the solution.

\begin{eqnarray*}
p(t)	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot \left(
		\left(\cos \theta + i \sin \theta \right)^t -
		\left(\cos \theta - i \sin \theta \right)^t
		\right) \\
	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot \left(
		\left(\cos t \theta + i \sin t \theta \right) -
		\left(\cos t \theta - i \sin t \theta \right)
		\right) \\
	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot
		\left( 2 i \sin t \theta \right) \\
	& = &	\frac{100}{\sqrt{1 - \left(\frac{c}{2}\right)^2}} \cdot
		\left( \sin t \theta \right) \\
	& = &	\frac{100 \sin t \theta}{\sin \theta}
\end{eqnarray*}

The final solution is

\begin{eqnarray*}
p(t)	& = &	\frac{100 \sin t \theta}{\sin \theta}
\end{eqnarray*}

where $\theta = \arccos(\frac{1.99}{2})$.
}

\problempart Does the Doritofier missle hit earth?

\solution{

The solution indicates that the path of the Doritofier is a sine wave
with amplitude

\begin{eqnarray*}
\frac{100}{\sin \theta}
	& = &	\frac{100}{\sin \arccos\left(\frac{c}{2}\right)} \\
	& = &	\frac{100}{\sqrt{1 - \left(\frac{c}{2}\right)^2}} \\
	& = &	\frac{100}{\sqrt{1 - \left(\frac{1.99}{2}\right)^2}} \\
	& = &	1001.253\ldots
\end{eqnarray*}

Since Earth is 1010 units from Xoros 19, we're safe.

\bigskip

On the other hand, since the path of the missle is a sine wave, it
{\em will} be returning to Xorox 19 presently...}

\end{problemparts}


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

%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems

%%%%%%%%%%%%%%%%  S99 ps6


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


\problem {\bf (30 points)} 

Use the Master Theorem to find a $\Theta()$ bound on the solution to each
of the following recurrences:

\begin{enumerate}
\item[(a)]
$T(n) = 8T(\lfloor n/2\rfloor) + n^3$
\item[(b)]
$T(n) = 2T(\lfloor n/3\rfloor) + n$
\item[(c)]
$T(n) = 16T(\lfloor n/4\rfloor) + n\log n$
\item[(d)]
$T(n) = 2T(\lfloor n/4\rfloor) + \sqrt{n}$
\item[(e)]
$T(n) = 4T(\lfloor n/3\rfloor) + 1$
\item[(f)]
$T(n) = \pi*T(\lfloor n/\pi^3\rfloor) + n^{1/3}$
\end{enumerate}

\solution{
a. $(n^3)\log n$
\,\,\, (master theorem case 2)
\\
b. $n$
\,\,\, (master theorem case 3)
\\
c. $n^2$
\,\,\, (master theorem case 1)
\\
d. $\sqrt{n}*\log n$
\,\,\, (master theorem case 2)
\\
e. $n^{\log_3(4)}$
\,\,\, (master theorem case 1)
\\
f. $(n^{1/3})*\log n$
\,\,\, (master theorem case 2)
}

\problem {\bf (14 points)}

Consider the recurrence: $T(n) = 2*T(\lfloor\sqrt{n}\rfloor) + 1$

\begin{enumerate}
\item[(a)]

Make a substitution of the form $n = f(m)$ to turn this into a
recurrence to which one can apply the Master Theorem.
(Such recurrences are called ``divide and conquer'' recurrences).

\item[(b)] Give tight asymptotic bounds on $T(n)$.
(Hint: If you find it helpful to assume that $T(n)$ is a
non-decreasing function on positive integers, you may go ahead and
assume this without giving an argument why it is true.)

\solution{
Substitute $n = 2^m$ and get $U(m) = 2U(\lfloor m/2\rfloor) + 1$. Thus
$U(m) = \theta(m) = \theta(\log n)$


Define 
$U(m)=T(2^m)$, a function on integer $m$ only.

Then you argue that $U(m)=\theta(m)$.
This implies that 
$\exists_{c_1,c_2,m_0}\, \forall_{m\geq{m_0}}$
the following holds:

$$c_1 m \leq U(m) \leq c_2 m$$

because $T()$ is non-decreasing, we have:

$$T(2^{\lfloor \log_2 n\rfloor})
\leq 
T( n ) 
\leq 
T(2^{\lceil \log_2 n\rceil})$$

Now we can develop the left side of this equation:

$$T(n)\geq 
T(2^{\lfloor \log_2 n\rfloor})
=
U(\lfloor \log_2 n\rfloor)
\geq
c_1 \lfloor \log_2 n \rfloor 
\geq 
c_1 \log_2 n - c_1
\geq
c_1' \log_2 n
$$
for all $n\geq{n_0}$ for some $n_0$.

And similarly the right side:

$$T(n)\leq 
T(2^{\lceil \log_2 n\rceil})
=
U(\lceil \log_2 n\rceil)
\leq
c_2 \lceil \log_2 n \rceil 
\leq 
c_2 \log_2 n + c_1
\leq
c_2' \log_2 n
$$
for all $n\geq{n_0'}$ for some $n_0'$.

}

\end{enumerate}



\problem {\bf (30 points)}

Matt looks at merge sort algorithm from his 6.042 lecture and asks
"What is so special about 2 lists? Why can't I divide the list into
$k$ sublists to sort recursively and than merge these together?" He
calls his new algorithm the k-Merge Sort.

\begin{enumerate}

\item[(a)]
Show that by using an analogous procedure to the one used to merging
two lists, the worst case time to merge $k$ lists of total size $n$ is
at most $(k-1)n$.

\solution{
there are at least two ways to do a k-list merging procedure
which is ``analogous to 2-list merging'': 
\begin{enumerate}
\item
Use the usual procedure to merge two lists of $x$ elements total, to
merge lists 1 and 2 into 2' (worst number of comparisons is
$2(n/k)-1$), and then 2' and 3 into 3' (worst number of comparisons is
$3(n/k)-1$, etc, up to merging list (k-1)' and list k into the final
answer (worst number of comparisons is $(k-1)(n/k)-1$).

Hence the total number of comparisons can be upper bounded by
$(n/k)(2+3+...+(k-1))=(n/k)(k(k-1)/2)=n(k-1)/2$
\item
Look at the first elements in all k lists and identify/eliminate the
largest (assume the lists are sorted in decreasing order).  This takes
at most $k-1$ comparisons.  Every time you do this, you eliminate one
element, so you will do this at most $n$ times.  Hence the upper bound
is $n(k-1)$.
\end{enumerate}
}

\item[(b)]
Assume from now that the worst case time to merge $k$ lists of total
size $n$ is simply equal to $(k-1)n$.  Write down a recurrence for the
worst case time of k-Merge Sort.

\solution{$T(n) = k*T(n/k) + (k-1)n$}

\item[(c)]
Show that the running time of k-Merge Sort is $cn+(k-1)n\log_k(n)$ for
some constant $c$ independent of $k$.  (Hint: use the Plug and Chug
method). For what value of $k$ is the algorithm fastest?

\solution{
$T(n) = k*T(n/k) + (k-1)n = k*(k*T(n/k^2) + (k-1)*(n/k)) + (k-1)n = k^2*T(n/k^2) +
2(k-1)n = k^i*T(n/k^i) + i(k-1)n = k^{\log_k(n)}*T(1) + {\log_k(n)}*(k-1)n =
cn+(k-1)n\log_k(n)$

Fastest for minimal $(k-1)n\log_k(n)$, which is the same as minimal
$(k-1)/(\ln k)$, which is for $k=2$.}

\end{enumerate}

Matt thinks he can improve his algorithm by using divide-and-conquer
during the merge phase as well.  He suggests recursively merging k/2
of the sublists at a time and then using the old procedure to merge
the resulting two lists.

\begin{enumerate}

\item[(d)]
Using the notation $M(n,k)$ to denote the time it takes to merge $k$
lists of total size $n$ (each list has $n/k$ elements), Matt comes up
with the recurrence:

\[
M(n,k) = 2*M(n/2, k/2) + (n-1)
\]

Explain how he got this equation.

\solution{
Twice the time it takes to run this procedure recursively on the set
of $k/2$ lists, and $n-1$ time for mergining the resulting two
$n/2$-element lists.}

\item[(e)]
Show that $M(n,k)=\theta(n\log_2(k))$ for $k\leq{n}$.

\solution{
$M(n, k) 
= 2^i*M(n/2^i, k/2^i) + i*n - (1+2+4+...+2^{i-1})
= 2^{\log_2(k)}*M(n/k, 1) + \log_2(k)*n - (2^{\log_2(k)}-1)
= k*\theta(1) + n\log_2(k) - (k-1)
= \theta(n\log_2(k))$ 
(if $k \leq n$)
}

\item[(f)]
What is the running time of k-Merge Sort using this new merging procedure?
How does it compare with the 2-Merge Sort previously done in lecture?


\solution{
New recurrence is $T(n) = k*T(n/k) + n*\log_2(k)$.  So $T(n) =
n*\log_2(k)*\log_k(n) = n*\log_2(n)$, independently of $k$.
}

\end{enumerate}



\problem {\bf (26 points)}

\noindent
Consider a set of record items, each carrying some data and a key.  We
define a {\em majority key} in such a set:


\begin{quote}
{\bf Definition:} The {\em majority key} of a set of $n$ records is a
key that occurs more than $n/2$ times.  

\noindent
(E.g.: $2$ is the majority key in a set of 3 records which are tagged,
consecutively, by keys $1$, $2$, and $2$.  On the other hand, in the
set of 4 records tagged by keys $1$, $2$, $3$, and $3$, there is no
majority key.)
\end{quote}

Consider the following algorithm for finding the majority key of a set of
records: If there is an even number of records, we pair adjacent items up
(first with second, third with fourth, etc.) and compare their keys.  If
they have the same key, we keep one of them, otherwise we throw them both
away.  We run this algorithm recursively on the resulting set.  If there
is an odd number of items in our set, we find the majority key of the set
containing all but the last item.  If there was no majority key than we
check if the key of the last record is the majority key by explicitly
counting how many times this key appears in the whole set.  We continue in
this fashion until we either get one record, in which case we check if its
key is in fact the majority key --- again by counting how many times this
key appears in the original set --- or we end up with no items, in which
case we conclude that there was no majority key.

\begin{enumerate}

\item[(a)]
Prove that if there is a majority key in the initial set of records
then this algorithm terminates with a record item carrying that key.
(Hint: Find an invariant that is preserved at every stage.  Consider
the even and odd cases separately.)

\solution{

Case 1: Even number of elements $= 2k$.  Element t occurs at least
$2k+1$ times.  After we pair the elements into k pairs, suppose
l pairs have two different elements and $k-l$ pairs have two
same elements.  Of the l different pairs, there is at most 1 t in
each pair, therefore at most l t's are taken away.  Hence, the same
elements have at least $k-l+1$ t's out of $2k-2l$ elements.  So, t is
a majority element now and it still will be after dividing the number
of elements by 2.

Case 2: Odd number of elements $=2k+1$.  If the last element is not t,
then t occurs $k+1$ times in the first $2k$, i.e. t is a majority
element of the first $2k$ and we can see case 1.

If the last element is t, than t may not be a majority element of the
first $2k$, but the first $2k$ can have no other majority element so
the algorithm will return either t or no majority, and in the latter
case we discover t is the majority element in the checking phase.}

\item[(b)]
Write down a recurrence for worst-case time this algorithm takes.  For
this part assume that the size of the working set at every stage is
even.

\solution{
$T(n)=T(n/2)+n/2$
}

\item[(c)]  
Solve the recurrence you wrote down in part (b) to obtain an
asymptotic time bound (theta) for worst-case running time.  (We are
interested in the {\em order} of growth, not the exact constant.)

\solution{
$T(n)=T(n/2)+n/2=T(n/4)+n/4+n/2=...=\theta(n)$
}

\item[(d)]
Argue that this time bound also holds without the assumption that the
working set at each stage is even.

\solution{
If the set is odd, then
$T(n)=T(n/2)+n/2+n=T(n/2)+3/2n$
which comes down to $T(n)=3n=\theta(n)$}

\end{enumerate}


\problem


The running time of algorithm A is described by the recurrence
T(n) = 16 T(n/4) + n^2.  A competing algorithm A? has a running
time T?(n) = aT?(n/2) + n^2.  What values of a ensure that algorithm
A has a better time asymptotically?



%%%%%%%%%%%%%%%%%%%% S99 ps7



\problem {\bf (25 points) } Solve the following linear recurrences.

\begin{problemparts}

\problempart {\bf (5 points)}
\begin{eqnarray*}
T_0 & = & 0 \\ T_1 & = & 1 \\ T_n & = & 2 T_{n-1} + 3 T_{n-2} \quad
\quad \text{(for $n \geq 2$)}
\end{eqnarray*}

\solution{The characteristic equation is $r^2 - 2 r - 3 = 0$, which
has roots $r = -1$ and $r = 3$.  Therefore, the general form of the
solution is $T_n = A \cdot (-1)^n + B \cdot 3^n$.  Substituting the
base cases into this general form gives a system of equations:

\begin{eqnarray*}
0	& = &	A + B \\
1	& = &	-A + 3B
\end{eqnarray*}

The solution to this system is $A = -\frac{1}{4}$ and $B =
\frac{1}{4}$.  Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
T_n & = & -\frac{1}{4} \cdot (-1)^n + \frac{1}{4} \cdot 3^n
\end{eqnarray*}
}

\problempart {\bf (10 points)}
\begin{eqnarray*}
T_0 & = & 0 \\
T_1 & = & 1 \\
T_n & = & 2 T_{n-1} + 3 T_{n-2} + n \quad \quad \text{(for $n \geq 2$)}
\end{eqnarray*}

\solution{The characteristic equation is the same as before.
Therefore, the general form of the homogeneous solution is still $T_n
= A \cdot (-1)^n + B \cdot 3^n$.  Let's first look for a particular
solution of the form $an + b$.

\begin{eqnarray*}
an+b	& = &	2(a(n-1)+b) + 3(a(n-2)+b) + n \\
	& = &	2an - 2a + 2b + 3an - 6a + 3b + n \\
\end{eqnarray*}

Equating linear terms gives $a = - \frac{1}{4}$ and equating constant
terms gives $b = - \frac{1}{2}$.  This suggests the particular
solution $- \frac{1}{4} n - \frac{1}{2}$, which we can verify by
substituting back into the recurrence.  The general form of the
complete solution is therefore $T_n = A \cdot (-1)^n + B \cdot 3^n -
\frac{1}{4} n - \frac{1}{2}$.  Substituting the base cases into this
general form gives a system of equations:

\begin{eqnarray*}
0	& = &	A + B - \frac{1}{2} \\
1	& = &	-A + 3B - \frac{3}{4}
\end{eqnarray*}

The solution to this system is $A = - \frac{1}{16}$ and $B =
\frac{9}{16}$.  Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
T_n = - \frac{1}{16} \cdot (-1)^n + \frac{9}{16} \cdot 3^n - \frac{1}{4} n - \frac{1}{2}
\end{eqnarray*}
}

\problempart {\bf (10 points)}
\begin{eqnarray*}
T_0 & = & 0 \\
T_1 & = & 1 \\
T_2 & = & 2 \\
T_n & = & 2 T_{n-1} + 4 T_{n-2} - 8 T_{n-3} \quad \quad \text{(for $n \geq 3$)}
\end{eqnarray*}

\solution{The characteristic equation is $r^3 - 2 r^2 - 4 r + 8 = 0$,
which has a root at $r = -2$ and a double root at $r = 2$.  Therefore,
the general form of the solution is

\begin{eqnarray*}
T_n & = & A \cdot (-2)^n + B \cdot 2^n + C \cdot n 2^n.
\end{eqnarray*}

Substituting the base cases into this general form gives the following
system of equations.

\begin{eqnarray*}
0	& = &	A + B \\
1	& = &	-2A + 2B + 2C \\
2	& = &	4A + 4B + 8C
\end{eqnarray*}

The solution to this system of equation is $A = - \frac{1}{8}$, $B =
\frac{1}{8}$, and $C = \frac{1}{4}$.  Therefore, the complete solution
to the recurrence is

\begin{eqnarray*}
T_n & = & - \frac{1}{8} \cdot (-2)^n + \frac{1}{8} \cdot 2^n + \frac{1}{4} \cdot n 2^n.
\end{eqnarray*}
}

\end{problemparts}

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

\problem {\bf (10 points) } Suppose that the catch of lobsters each
year is the average of the catch for the last two years.  The catch in
year 0 was 1000 pounds and the catch in year 1 was 2500 pounds.

\begin{problemparts}
\problempart Express the catch of lobsters in year $n$ using
a recurrence relation and sufficient base cases.

\solution{
\begin{eqnarray*}
L_0 & = & 1000 \\
L_1 & = & 2500 \\
L_n & = & \frac{L_{n-1} + L_{n-2}}{2} \quad \quad (n \geq 2)
\end{eqnarray*}
}

\problempart Solve the recurrence to determine the catch in year $n$.

\solution{The characteristic equation is $2 r^2 - r - 1 = 0$.  This
equation has roots $r = 1$ and $r = - \frac{1}{2}$.  Thus, the
solution has the form

\begin{eqnarray*}
L_n	& = &	A \cdot 1^n + B \cdot \left(- \frac{1}{2} \right)^n.
\end{eqnarray*}

Substituting the base cases gives a system of linear equations:

\begin{eqnarray*}
1000	& = &	A + B \\
2500	& = &	A - \frac{1}{2} B
\end{eqnarray*}

Solving these equations gives $A = 2000$ and $B = -1000$.  Thus the
complete solutions is

\begin{eqnarray*}
L_n & = & 2000 - 1000 \cdot \left(- \frac{1}{2} \right)^n.
\end{eqnarray*}
}

\problempart What constant will the annual lobster catch approach in
the distant future?

\solution{
\begin{eqnarray*}
\lim_{n \rightarrow \infty} 2000 - 1000 \cdot \left(- \frac{1}{2} \right)^n
	& = &	2000 \text{ pounds per year}
\end{eqnarray*}
}

\end{problemparts}



%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems


\end{problems}

\end{document}



