%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spring98 final #2 (added by Ivan)
\problem\points{15} Let $T:\nats\to\nats$ be defined by the following
recurrence.  Prove that $T(n)= \Theta(n)$. \hint Find a constant $A$ such
that $T(n) \le An $ for all $n > 0$.

\begin{displaymath}
T(n) = 
\begin{cases}
8  & \text{if $n < 5$},\\
T\left(\floor{\frac{n}{5}}\right)+T\left(\floor{\frac{3n}{4}}\right)+8n
&  \text{if $n \ge 5$}.\\
\end{cases}
\end{displaymath}

\solution{
\textbf{Solution:} $T(n) \le (19/20)An + 8n = n(19/20A +8) \le An$,
providing $8 \le A/20$, so $A\ge 160$ will work.  Since $T(n) \ge 8n$, we
have $T= \Theta(n)$.  ($T(n) \ge 8n$ follows assuming $T\ge 0$ which we'll
take for granted; it's easy to verify by induction).
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%prelude to spring98 final #8,9 (added by Ivan)
\end{problems}
The next two problems are based on the following scenario: an urn contains red,
white and blue colored balls.  The fraction of red, white, and blue balls
is $r,w,b$, respectively (so $r + w + b =1$).  A gambler repeatedly pulls
a ball at random from the urn.  That is, at any point during succesive
pulls, each ball in the urn is equally likely to be the next one pulled.
The gambler puts the ball back into the urn before making the next pull.
He keeps pulling balls until he pulls \emph{two red balls in a row}.
\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spring98 final #8 (added by Ivan)
\problem\points{25}
\bparts

\ppart\points{5} Let $N_n$ be the event that at least $n$ balls have been
pulled and the $n$th ball is \emph{not} red; let $p_n = \pr{N_n}$.  Write
an expression in terms of $p_n$ for the probability that the Gambler stops
pulling after exactly $n+2$ balls.

\solution{
\textbf{Solution}: $r^2p_n$, because the Gambler stops at step $n+2$ iff he
pulls $n$ balls with the $n$th ball not red (probability $p_n$), and then
he pulls two reds in a row (probability $r^2$).
}

\ppart\points{10} Write a linear homogeneous recurrence equation for
$p_{n+2}$ in terms of $p_{n+1}$ and $p_n$.

\solution{
\textbf{Solution}: \[p_{n+2} = (1-r)p_{n+1} + (1-r)rp_n.\]

To see why, suppose $N_{n+2}$ occurred.  Consider whether the $n+1$st pull
was red.  The probability the Gambler pulled non-red on the $n+1$st turn is
$p_{n+1}$, and the probability he pulled non-red again on the $n+2$nd turn
is therefore $(1-r)p_{n+1}$.  If the $n+1$st pull was red, then the
$n$th pull must have been non-red or the Gambler would have stopped at the
$n+1$st pull.  So the probability the $n+1$st pull was red and the $n+2$nd
pull was non-red is $r(1-r)$ times the probability, $p_n$, that the $n$th
pull was non-red.
}

\ppart\points{5} Suppose $r=2/3$.  Write a closed form expression for 
$p_n$.

\medskip
\solution{
\textbf{Solution}: The characteristic equation $x^2 - (1-r)x - (1-r)r =
x^2 - x/3 - 2/9 = 0$ has roots $r= 2/3, -1/3$, so $p_n = A(2/3)^n +
B(-1/3)^n$.  The initial conditions are that $p_1$ is the probability of
throwing a non-red on the first throw, namely $p_1 = 1/3$.  Likewise,
$p_2$ is the probability of throwing a non-red on the second throw, namely
$p_2 = 1/3$.  So at $n=1$, $2A/3 - B/3 = 1/3$ which implies $2A= B+1$, and
at $n=2$, $3/9 = 4A/9 + B/9 $ so $3 = 4A + B = 2(B+1)+B=3B+2$ and $B=1/3,
A=2/3$.  Therefore,
\[p_n = (2/3)^{n+1} - (-1/3)^{n+1}.\]

\textbf{GRADING NOTE}.  To avoid ``double jeopardy,'' if a mistaken,
nondegenerate recurrence from the previous part was correctly solved, we
gave full credit on this part.
}

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Quiz 2
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{15} \textbf {Nonhomogenous Recurrence}

Give a closed-form solution to the following nonhomogenous recurrence
relation,

$$G_n = 2G_{n-2} + 2^{n-1}$$

such that $G_0 = 1$ and $G_1 = 2$.

\solution{\bigskip {\bf Solution:}
First we solve the homogenous part.  The characteristic equation
is 

$$r^2 - 2 = 0$$

so $r = \pm \sqrt{2}$ are the solutions.  Thus, our general solution is of 
the form $\alpha_1 \sqrt{2}^n + \alpha_2 (-\sqrt{2})^n$.  

For our particular solution, we guess that $c2^n$ will work, where $c$
is a constant.  Plugging in, this gives us

\begin{eqnarray*}
c2^n &=& 2c2^{n-2} + 2^{n-1}\\
     &=& c2^{n-1} + 2^{n-1}\\
2c2^{n-1} &=& c2^{n-1} + 2^{n-1}\\
c2^{n-1} &=& 2^{n-1}\\
c &=& 1
\end{eqnarray*}

So we must now solve for $\alpha_1$ and $\alpha_2$ such that

$\alpha_1 + \alpha_2 + 2^0 = \alpha_1+\alpha_2 +1 = 1$

Therefore, $\alpha_2 = -\alpha_1$.  Furthermore, 

$$\sqrt{2}\alpha_1 + (-\sqrt{2})(-\alpha_1) + 2^1 = 2\sqrt{2}\alpha_1 + 2 = 2$$

so $\alpha_1 = \alpha_2 = 0$ are our solutions.  So the
closed form solution for the recurrence relation is just

$$G_n = 2^n.$$

}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Quiz 2
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \pts{35} \textbf {3-coloring Grid Graphs}

In Exam 1, we proved that an $m$ by $n$ grid graph is always
2-colorable.  Thus, it must be 3-colorable.  However, with 3 colors,
we suddenly get a lot of choices for how to color the graph.  In this
problem we will solve the question ``How many ways are there
to 3-color a $3$ by $n$ grid graph?''

(Recall that a 3-coloring of a graph is an assignment of one of three
colors to each vertex in the graph such that if two vertices are
connected by an edge, they must have different colors.  We consider
two 3-colorings different if any vertex is colored differently between
the two.)

\problempart {\bf (8 points)} Suppose we want to color the
graph by first coloring the first $n-1$ columns, then choosing a
coloring for the last column.  However, the number of ways we can
color the last column is dependent on which coloring we choose.  There are
two cases to consider.

\begin{figure}[htbp]
\centerline{\psfig{figure=3color.eps,height=1.5in}}
\end{figure}

In the first case, the vertices $(n-1,1)$ and $(n-1,3)$ are the same color.

In the second case, the vertices $(n-1,1), (n-1,2)$, and $(n-1,3)$
are all different colors.  

\begin{itemize}
\item[1.] How many ways can we color the last column in the first
case?  \underline{\hspace{1in}} \solution{5}

\item[2.] Of the ways to color the last column in the first case, how
many use three different colors? \underline{\hspace{1in}} \solution{2}

\item[3.] How many ways can we color the last column in the second case?
\underline{\hspace{1in}} \solution{4}

\item[4.] Of the ways to color the last column in the second case,
how many use three different colors? \underline{\hspace{1in}}
\solution{2}

\end{itemize}

\nextproblem

\problempart {\bf (10 points)} Let $A_n$ be the number of ways to
3-color a $3$ by $n$ grid graph such that the last column is colored
with only 2 colors.  Let $B_n$ be the number of ways to 3-color a $3$
by $n$ grid graph such that the last column is colored with three
different colors.

Formulate a system of recurrence relations for $A_n$ and $B_n$, and give
the initial values $A_1$ and $B_1$.

\solution{\bigskip
{\bf Solution:}

$A_n = 3A_{n-1} + 2B_{n-1}$.

$B_n = 2A_{n-1} + 2B_{n-1}$.

$A_1 = B_1 = 6.$
}

\mediumspace

\problempart {\bf (7 points)} Suppose that 

$$A_n = xc_1^n + yc_2^n$$
$$B_n = xd_1c_1^n + yd_2c_2^n$$

is the solution to the recurrence relation you found in part (b).
Find the number of ways to 3-color a 3 by $n$ grid graph 
in terms of $c_1, c_2, d_1, d_2$, and $n$ and no other variables.

\solution{\bigskip
{\bf Solution:}

Plugging in $A_1 = 6$ and $B_1 = 6$ we get that 
$xc_1 = 6 - yc_2$ so $6 = d_1(6-yc_2)+yd_2c_2$.  Solving for $y$ we get

$$y = \frac{6 - 6d_1}{(d_2 - d_1)c_2},$$

so 

$$x = \frac{-6 + 6d_2}{(d_2 - d_1)c_1}.$$

Finally, the number of ways to 3-color a 3 by $n$ grid graph is $A_n + B_n$
which is just

$$A_n+B_n = \left(\frac{-6+6d_2}{(d_2-d_1)c_1}\right)(1+d_1)c_1^n +
\left(\frac{6 - 6d_1}{(d_2-d_1)c_2}\right)(1+d_2)c_2^n$$

this can be simplified a bit, to 

$$A_n+B_n = 6(d_1+1)\left(\frac{d_2-1}{d_2-d_1}\right)c_1^{n-1} -
6(d_2+1)\left(\frac{d_1-1}{d_2-d_1}\right)c_2^{n-1}.$$

}


\nextproblem

\problempart {\bf (10 points)}  Find $c_1, c_2, d_1,$ and $d_2$ such that

$$A_n = xc_1^n + yc_2^n$$
$$B_n = xd_1c_1^n + yd_2c_2^n$$

is the general form for the system of recurrence relations you found in 
part (b).  

\solution{\bigskip
{\bf Solution:}

Let's guess that for some $c \neq 0$ and some $d$, that $A_n = c^n$
and $B_n = dc^n$.  Then, substituting into the recurrence relation
yields

$$c^n = 3c^{n-1} + 2dc^{n-1}$$

and 

$$dc^n = 3c^{n-1} + 2dc^{n-1}$$

Dividing the top equation by $c^{n-1}$ yields $c = 3+2d$.  Subsituting
this into the bottom equation and gathering terms yields $2d^2 + d - 2 = 0$,
so 

$$d = \frac{-1 \pm \sqrt{17}}{4}.$$

This gives two solutions, $c_1 = \frac{5+\sqrt{17}}{2}, d_1 =
\frac{-1+\sqrt{17}}{4}$ and $c_2 = \frac{5-\sqrt{17}}{2}, d_2 =
\frac{-1-\sqrt{17}}{4}$.  

This was not required by the question, but for a sense of
completeness, using these values and simplifying, the number of ways
to 3-color a 3 by $n$ grid graph is

$$\left(\frac{9+3\sqrt{17}}{2\sqrt{17}}\right) \left( \frac{5+
\sqrt{17}}{2} \right)^n +
\left(\frac{-9+3\sqrt{17}}{2\sqrt{17}}\right) \left( \frac{5-
\sqrt{17}}{2} \right)^n.$$



}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Midterm
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


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

\begin{problemparts}

\problempart {\bf (5 points)} Find a closed-form solution to the
following recurrence equation.

\begin{eqnarray*}
y_0 & = & 0 \\
y_1 & = & 1 \\
y_n & = & 7 y_{n-1} - 12 y_{n-2} + 1 \quad \text{(for $n \geq 2$)}
\end{eqnarray*}

\examonly{\vspace{2.5in}}

\solution{ The characteristic equation is $r^2 - 7 r + 12 = 0$.  The
roots of this equation are $r = 3$ and $r = 4$.  Therefore, the
solution to the homogenous equation has the form:

\begin{eqnarray*}
y_n & = & A 3^n + B 4^n
\end{eqnarray*}

The inhomogenous term is a constant, so we first guess a constant
particular solution.  Setting $y_n = c$ gives:

\begin{eqnarray*}
c   & = &   7 c - 12 c + 1 \\
6 c & = &   1 \\
c   & = &   \frac{1}{6}
\end{eqnarray*}

The complete solution has the form:

\begin{eqnarray*}
y_n & = &   A 3^n + B 4^n + \frac{1}{6}
\end{eqnarray*}

Substituting the base cases into this general form gives a system of
linear equations:

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

The solution to this system is $A = - \frac{3}{2}$ and $B =
\frac{4}{3}$.  The complete solution to the inhomogenous recurrence is
therefore:

\begin{eqnarray*}
y_n & = & - \frac{3}{2} \cdot 3^n + \frac{4}{3} \cdot 4^n + \frac{1}{6}
\end{eqnarray*}
}

\problempart {\bf (5 points)} Give a $\Theta$ bound on the solution to the
following recurrence.  For reference, $\ln 7 \approx 1.9$ and $\ln 8
\approx 2.1$.

\begin{eqnarray*}
T(n)    & = &   8 T\left(\frac{7n}{8}\right) + n \sqrt{n}
\end{eqnarray*}

\solution{
We use Akra-Bazzi.  First, we find $p$.

\begin{eqnarray*}
8 \cdot \left(\frac{7}{8}\right)^p & = & 1 \\
8 \cdot 7^p & = & 8^p \\
\ln 8 + p \ln 7 & = & p \ln 8 \\
p & = & \frac{\ln 8}{\ln 8 - \ln 7} \\
  & = & 15.572\ldots
\end{eqnarray*}

An integration gives the $\Theta$ bound:

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

The final step uses the fact that $p \geq \frac{3}{2}$.
}

\end{problemparts}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Midterm
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\problem {\bf (8 points)}  The inhabitants of Xoros 19 are unsatisfied
with the performance of their Fritolator devices.  They have
constructed a factory to convert Fritolators into new, more deadly
craft.  Each day, the factory performs one of the following
conversions:

\begin{eqnarray*}
\text{1 Fritolator} & \rightarrow & \text{1 Pringlizer} \\
\text{2 Fritolators} & \rightarrow & \text{1 Tostitomatic} \\
\text{2 Fritolators} & \rightarrow & \text{1 Santitotron}
\end{eqnarray*}

Grzzwk, the ruler of Xoros 19, plans to use the factory to convert his
entire fleet of $n$ Fritolators.  However, he must decide the sequence
of ships that the factory will produce.  Such a sequence is called a
{\em conversion schedule}.  For example, there are 5 possible
conversion schedules for a fleet of $n = 3$ Fritolators:

\begin{enumerate}
\item Pringlizer, Pringlizer, Pringlizer
\unspace
\item Pringlizer, Tostitomatic
\unspace
\item Pringlizer, Santitotron
\unspace
\item Tostitomatic, Pringlizer
\unspace
\item Santitotron, Pringlizer
\unspace
\end{enumerate}

\bigskip

\begin{problemparts}

\problempart {\bf (4 points)} Let $x_n$ be the number of possible conversion
schedules for a fleet of $n$ Fritolators.  Express $x_n$ with a
recurrence relation and sufficient base cases.

\examonly{\vspace{1in}}

\solution{
If $n = 0$, then there is a single conversion schedule; namely,
produce nothing.  If $n = 1$, then there is still only one conversion
schedule; the factory must produce a Pringlizer.  If $n \geq 2$, then
every conversion schedule is one of the following:

\begin{enumerate}
\item A Pringlizer followed by a conversion schedule for $n-1$ Fritolators.
\item A Tostitomatic followed by a conversion schedule for $n-2$ Fritolators.
\item A Santitotron followed by a conversion schedule for $n-2$ Fritolators.
\end{enumerate}

Thus, for a fleet of $n \geq 2$ Fritolators, there are $x_{n-1} + 2
x_{n-2}$ conversion schedules.  In summary:

\begin{eqnarray*}
x_0 & = & 1 \\
x_1 & = & 1 \\
x_n & = & x_{n-1} + 2 x_{n-2} \quad \text{(for $n \geq 2$)}
\end{eqnarray*}
}

\problempart {\bf (4 points)} Find a closed-form expression for $x_n$, the
number of conversion schedules for a fleet of $n$ Fritolators.

\solution{ The characteristic equation is $r^2 - r - 2 = 0$.  The
roots of this equation are $r = 2$ and $r = -1$.  The general form of
the solution is therefore

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

Substituting the base cases into this general form gives two linear
equations:

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

The solution to this system of equations is $A = \frac{2}{3}$ and $B =
\frac{1}{3}$.  Plugging these constants back into the general form of
the solution gives the exact solution:

\begin{eqnarray*}
x_n & = &   \frac{2}{3} \cdot 2^n + \frac{1}{3} \cdot (-1)^n
\end{eqnarray*}
}
\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{10} \textbf {Recurrence Relations}

\problempart {\bf (5 points)}
Find a closed form solution to the following homogenous recurrence
relation,

$$ A_n = -A_{n-1} + A_{n-2} + A_{n-3} $$

such that $A_0 = 1, A_1 = 0,$ and $A_2 = 3$.

\solution{\bigskip{\bf Solution:}

The characteristic equation for this recurrence is 

$$r^3 + r^2 - r - 1 = 0$$

which factors to

$$(r+1)(r^2 - 1) = (r+1)^2(r-1) = 0.$$

So we get a closed form solution of the form

$$A_n = c_1 + c_2(-1)^n + c_3 n(-1)^n.$$

Using the initial conditions, we find that

$c_1 + c_2 = 1,$ so $c_2 = 1 - c_1$.

$c_1 - (1-c_1) - c_3 = 0$, so $c_3 = 2c_1 - 1$, and

$$c_1 + (1-c_1) + 2(2c_1 - 1) = 3$$

$$4c_1 + 1 - 2 = 3$$

$$4c_1 = 4$$

so $c_1 = 1$, $c_2 = 0$, and $c_3 = 1$.  Thus, the final answer is

$$A_n = 1 + n(-1)^n.$$
}

\mediumspace

\problempart {\bf (5 points)} Find a closed form solution to the
following inhomogenous recurrence relation:

$$ A_n = - A_{n-1} + A_{n-2} + A_{n-3} + 4 $$

where $A_0 = 1, A_1 = 0$, and $A_2 = 3$.

\solution{\bigskip{\bf Solution:}
We can use the general form for the homogenous part from part (a):

$$ A_n = c_1 + c_2(-1)^n + nc_3(-1)^n. $$

Now, let us guess a particular solution in the form $an+b$.

$$ an+b = a(n-3) + b + a(n-2) + b - a(n-1) - b + 4 $$
$$ an+b = an - 4a + b + 4 $$
$$ 0 = -4a + 4$$
$$ 4a = 4$$

So $a = 1$ and $b$ can be anything, so we will choose 0.  Now,
substituting the initial conditions, we get that

$c_1 + c_2 = 1$ so $c_2 = 1 - c_1$.

$c_1 - c_2 - c_3 + 1 = 0$, so $c_3 = 2c_1$, and

$c_1 + c_2 + 2c_3 + 2 = 3$, so

$c_1 + (1-c_1) + 4c_1 + 2 = 3$

$4c_1 + 3 = 3$, so $c_1 = 0$.  Thus, the solution is

$$A_n = (-1)^n + n$$.  }
