\documentclass[11pt]{article}
\usepackage{amsmath}
\input{macros-course}

\renewcommand{\solution}[1]{}

\newcommand{\Fib}{\mathop{\mbox{Fib}}}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
    \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\begin{document}

\handout{q2}{Quiz 2}{November 4, 1999}
%\handout{q2}{Quiz 1}{November 4, 1999}

\textbf{Your Name}:\ \mbox{}\hrulefill\mbox{}\par

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{lllll}
Yana Ageeva & Victor Boyko & Mary DeSouza & Sarfraz Khurshid & Mike Leonida\\
Ryan McCullough & Albert Meyer & Alantha Newman & Kyle Rose
\end{tabular}
\end{center}

\medskip

\begin{closeitemize}
\item This quiz is \textbf{CRIB SHEET ONLY}: no texts, other notes, or
technical aids.  There is an Appendix containing some useful facts you may
wish to look over quickly before starting the problems.

\item There are four (4) problems totaling 100 points. 
Problem parts are labelled with their point values.

\item Put your name on the top of {\bf every} page --- \emph{these pages
may be separated for grading}.

\item Write your solutions in the space provided.  If you need more
space, write on the back of the sheet containing the problem.  Please
keep your entire answer to a problem on that problem's page.

\item Unless a problem explicitly instructs otherwise, you may cite any of
the results from class in your solutions without reproving them.

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\hrule
\smallskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}
\smallskip
\hrule

\medskip

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
Problem & Points & Grade & Grader\\
& & & \\ \hline \hline
& & & \\
1 &  15 & & \\ & & & \\\hline & & &\\
2 &  35 & & \\ & & & \\\hline & & &\\
3 &  30 & & \\ & & & \\\hline & & &\\
4 &  20 & & \\ & & & \\\hline & & &\\
\hline
\hline
& & &\\
Total & 100 & & \\
& & &\\
\hline
\end{tabular}
\end{center}

\newpage

\begin{problems}


\problem \pts{15} A \emph{depth $n$ complete ternary tree} is a rooted
tree in which all paths from the root to a leaf have $n$ edges, and each
non-leaf node has 3 children.

\bparts

\ppart\pts{7}

Give a closed form formula for the number of nodes in the tree.

\solution{
The $i$th level of the tree contains $3^i$ nodes, so a depth $n$ tree
has
\[
\sum_{i=0}^{n} 3^i  =  \frac{3^{n+1} - 1}{3-1} =  \frac{3^{n+1} - 1}{2}.
\]
}

\vspace{2in}

\ppart\pts{8}  Prove that the number of nodes is $\Theta(3^n)$.

\solution{

$(3^{n+1}-1)/2 = O(3^n)$ because
\[
\frac{3^{n+1}-1}{2} < 3^{n+1} = 3\cdot 3^{n}
\]
for all $n \in \naturals$.

Conversely, $3^n = O((3^{n+1}-1)/2)$, because
\[
3^n < 3^n + 5 \leq 3^n + 3^n + 3^n - 1 = 3^{n+1} -1 = 2 \cdot \frac{3^{n+1}-1}{2}
\]
for $n$ such that $3^n \geq 3$, namely for $n >0$.

}

\vfill
\eparts

\newpage

\problem\pts{35} %\textbf{Graphs, Trees, State Machines, Counting, Well-order}

We apply the following operation to a simple graph $G$:
pick two vertices $u \neq v$ such that either
\begin{enumerate}
\item there is an edge of $G$ between $u$ and $v$ and there is also a path
from $u$ to $v$ which does \emph{not} include this edge; in this
case, delete the edge $\set{u,v}$.

\item there is no path from $u$ to $v$; in this case, add the edge
$\set{u,v}$.
\end{enumerate}

Keep repeating this operation until it is no longer possible to find two
vertices $u \neq v$ to which the operation applies.

Assume the vertices of $G$ are the integers $1,2,\dots,n$ for some $n \geq
2$.  This procedure can be modelled as a state machine whose states are
all possible simple graphs with vertices $1,2,\dots,n$.  $G$ is the start
state, and the final states are the graphs on which no operation is
possible.

\bparts
\ppart\pts{3}  Let $G$ be the graph with vertices $\set{1,2,3,4}$ and edges
\[
\set{\set{1,2},\set{3,4}}
\]
List the possible final states that are reachable from start state $G$: 

\solution{

It's not possible to delete any edge.  The procedure can only
add an edge connecting exactly one of vertices 1 or 2 to exactly one of
vertices 3 or 4.  So there are four final sets of edges, each containing
the edges $\set{1,2},\set{3,4}$ as well as one of the following edges:
\begin{enumerate}
\item $\set{1,3}$,
\item $\set{1,4}$,
\item $\set{2,3}$,
\item $\set{2,4}$.
\end{enumerate}
  }

\vspace{1in}

\iffalse
\ppart\pts{4} Now suppose $G$ is the graph with vertices $\set{1,2,3,4,5}$ and
edges
\[
\set{\set{1,2},\set{2,3},\set{3,1}, \set{4,5}}
\]
How many possible final states are there?   \brule{1.5in}

\solution{

Connect 4 or 5 to any one of 1, 2, and 3.  There are $2\cdot 3 =
6$ ways to do this.  Then delete any one of the edges between 1,2 and 3;
there are 3 ways to do this.  A total of $3 \cdot 6 = 18$ final states.

}
\fi


\ppart\pts{12} On the line next to each of the derived state variables
below, indicate the strongest property from the list below that it is
guaranteed to satisfy, no matter what starting graph $G$ is chosen.
\begin{center}
\begin{tabular}{cccccc}
invariant & increasing & decreasing & nonincreasing & nondecreasing & none
(may fluctuate)
\end{tabular}
\end{center}
The derived variables are:
\begin{enumerate}

\item[i)] the number of edges, \brule{1.5in}
\solution{fluctuates}

\item[ii)]  The number of connected components, \brule{1.5in}
\solution{nonincreasing}

\item[iii)]  the number of connected components plus the number of edges,
\brule{1.5in}
\solution{nonincreasing}

\item[iv)] the pair of numbers consisting of the number of connected
components and the number of edges; such pairs are ordered
lexicographically.  \brule{1.5in} \solution{decreasing}

\iffalse
\item[v)] the number of final states reachable from the current state, \brule{1.5in}
\solution{decreasing}
\fi

\end{enumerate}

\ppart\pts{7} Prove that any final state must be a tree on the set of
vertices.

\solution{

A final state must be connected, because otherwise there would be two
vertices with no path between them, and then a transition adding the edge
between them would be possible, contradicting finality of the state.

A final state can't have a cycle, because each transition deleting an edge
on the cycle would still be possible.
}

\vspace{2in}


\ppart\pts{7} Explain why, starting from any state, $G$, the procedure
terminates.

\solution{

The derived variable iv) takes pairs of natural numbers as values and is
decreasing under the lexicographic order on such pairs.  We know this
lexicographic order is a well-order, so the variable cannot decrease
forever.  This means the procedure must terminate.

To show that the variable decreases, note that the rule for deleting an
edge ensures that the connectedness relation does not change, so neither
does the number of connected components; therefore the first component of
the variable iv) does not change and the second component decreases by one
in a deletion move.  Hence the pair gets smaller.  The rule for adding an
edge ensures that the number of connected components decreases by one, and
under lexicographic order, this means the pair gets smaller (even though
the second component increases by one).

}

\vspace{3in}


\ppart\pts{6}
If $G$ is the complete graph on vertices $\set{1,2,3,4,5}$, how many final
states are there?  \brule{1.5in}

\solution{

125.  Every tree with vertices $\set{1,2,3,4,5}$ can be a final state.  We
know from Tutorial 9, Problem 2 that there are $5^{5-2}$ such trees.

}

\eparts

\newpage

\problem\pts{30}

\bparts

\ppart\pts{8} How many ways are there to seat $k$ children in $n\geq k$ chairs?
Express your answer as a simple formula using factorial notation.

\solution{

There are $n$ choices of chair for the first child, $n-1$ choices for the
second child, \dots, $n-(k-1)$ choices for the $k$th child, so by the
Product Rule, there are $n \cdot (n-1) \cdots (n-(k-1)) = n!/(n-k)!$ ways.

}

\vspace{1in}

\iffalse
\ppart\pts{5} Let $K_7$ be the complete graph on 7 vertices.  Does it have an
Eulerian circuit?  Briefly explain why or why not.

\solution{

Yes.  The degree of each vertex is 6, an even number, so we know there
exists an Eulerian circuit.

}

\vspace{1.5in}
\fi

\ppart\pts{8} Briefly explain why the sum of the degrees of the vertices
of a simple graph must be an even number.  Then explain why this implies
that there must be an even number of vertices whose degree is odd.

\solution{

In summing the degrees of the vertices, each edge. $\set{u,v}$, is counted
twice, once for vertex $u$ and once for $v$.  Hence the sum of the degrees
equals twice the number of edges, and hence is always even.

Now the sum of the degrees of the vertices with even degree is obviously
even, and the overall sum is even, so the sum of the degrees of the
remaining vertices, that is, the vertices with odd degree, must be even.
The only way a sum of odd numbers can be even is if there are an even
number of them, so there are an even number of vertices with odd degree.

}

\vspace{3in}

\ppart\pts{14}

Give a closed-form expression for $\sum_{i=0}^{\infty} ix^i$, assuming
$|x| < 1$, and explain how your answer was reached.

\solution{

We know that $\sum_{i=0}^{\infty} x^i= 1/(1-x)$.
Now, since the derivative  of $x^i$ is $ix^{i-1}$, we have
\begin{eqnarray*}
\sum_{i=0}^{\infty} ix^i & = & x\sum_{i=0}^{\infty} ix^{i-1}\\
& = & x\sum_{i=0}^{\infty} \frac{d(x^{i})}{dx}\\ 
& = & x \cdot \frac{d(\sum_{i=0}^{\infty} x^{i})}{dx}\\
& = & x \frac{d((1-x)^{-1})}{dx}\\
& = & \frac{x}{(1-x)^2}
\end{eqnarray*}

Other solutions follow by applying the ``perturbation method'' from
lecture notes, or by using the formula for $\sum_{i=1}^n ir^i$ in the
Appendix and taking limits as $n \to \infty$.

}

\vspace{3in}


\eparts

\newpage
\problem\pts{20} There are five different video games that are Student
Center favorites.  Two cost \$1.00 to play, and three cost \$2.00:

\begin{tabular}{ll}
Ms. PacMan & \$1,\\
Spy Hunter & \$1,\\
Street Fighter II & \$2,\\
Mortal Kombat & \$2,\\
VirtualFighter & \$2.
\end{tabular}

Andy Addict regularly plays these games in a sequence until he runs out of
money.  For example, when Andy has \$2.00 to spend, there are seven
possible sequences of games he can play:

\begin{tabular}{l}
(Ms. Pacman, Ms. Pacman),\\
(Ms. Pacman, Spy Hunter),\\
(Spy Hunter, Ms. Pacman),\\
(Spy Hunter, Spy Hunter),\\
(Street Fighter II),\\
(Mortal Kombat)\\
(VirtualFighter).
\end{tabular}

When Andy has \$3.00, there are quite a few more sequences he can play,
for example,

\begin{tabular}{l}
(Ms. Pacman, Ms. Pacman, Ms. Pacman),\\
(Ms. Pacman, Ms. Pacman, Spy Hunter),\\
\vdots\\
(Street Fighter II, Ms. Pacman),\\
\vdots\\
(Spy Hunter, VirtualFighter).
\end{tabular}

\iffalse

\bparts

\ppart\pts{2} How many sequences of play are there with a \$3.00 budget?
\brule{0.5in}

\solution{$2^3 + 2\cdot 3 +  3\cdot 2 = 20$.}

\vspace{0.5in}

\eparts

\fi

Let $P_{n}$ be the number of sequences that Andy can play for $n$ dollars.

\bparts

\ppart\pts{7} Exhibit a homogeneous linear recurrence for $P_{n}$.

\solution{ 

$P_n = 2P_{n-1} + 3P_{n-2}.$

}

\vspace{1in}

\ppart\pts{7} What is the general solution to your recurrence, ignoring
initial conditions?

\solution{

The charcteristic polynomial of the recurrence above is
$x^2-2x-3$.  It has two solutions $x=3$ and $x=-1$.  Thus, all solutions of
the recurrence will be of the form, $c3^n +d(-1)^n$.

}

\vspace{1in}

\iffalse
\ppart\pts{2} Describe initial conditions that uniquely determine the
values of $P_n$.

\solution{

Initial conditions: Any two consecutive values among $P_0 = 1,
P_1=2, P_2 = 7, P_3 = 20$.

}


\vspace{1in}
\fi

\ppart\pts{6} Find a closed form solution for $P_n$ satisfying the
appropriate initial conditions.

\solution{

Initial conditions: any two consecutive values among $P_0 = 1, P_1=2, P_2
= 7, P_3 = 20$.

Solving for the boundary conditions at $n=0,1$, we get
\[
c+d = 1, 3c-d = 2,
\]
so $c=3/4$ and $d=1/4$.  Thus, the final solution is
\[
P_n = 3/4\cdot 3^n + 1/4\cdot (-1)^n.
\]
}

\vspace{2in}
\eparts

\end{problems}

\newpage

\section*{Appendix}

A \textbf{simple graph} is an undirected graph with no self loops and at
most one edge between any two nodes.

A \textbf{tree} is a connected, acyclic simple graph.

An \textbf{Eulerian circuit} in a graph is a path beginning and ending at
the same vertex and containing each edge exactly once.

The \textbf{complete graph}, $K_n$, is the simple graph with $n$ vertices and
with an edge between every two vertices.

The \textbf{degree} of a vertex in a graph is the number of edges at the vertex.

\textbf{Lexicographic order}, $\preceq$, on pairs of natural numbers is
defined by the rule that
\[
(n_1,n_2) \preceq (m_1,m_2) \quad \mbox{iff} \quad [(n_1 < m_1) \mbox{ or } (n_1
= m_1 \mbox{ and } n_2 \leq m_2)].
\]

\[
\sum_{i=0}^n r^i = \frac{r^{n+1} - 1}{r-1}.
\]

\[
\sum_{i=0}^{n} ir^i = \frac{{r - (n+1) r^{n+1} + n r^{n+2}}}{(1-r)^2}.
\]

\[
\int \ln x dx = x \ln (x/e).
\]

\textbf{Stirling's formula}:
\[
n! \sim  \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n.
\]

\textbf{The Principle of Inclusion-Exclusion}:
\[
\card{\Union_{i=1}^n A_i}
= \sum_{S \subset \set{1,\dots,n}}
           (-1)^{\card{S}} \card{\Intersect_{j \in S} A_j}
\]

\iffalse

\section*{NOT PART OF QUIZ}

{\bf Topics to be Covered:}
\begin{itemize}

\item Graphs and Trees, 
\item Relations and Posets,
\item State Machines,
\item Sums and Series,
\item O, Theta, Stirling,
\item Linear Recurrences,
\item Permutations + General inclusion-exclusion (Light)

\end{itemize}
\fi

\end{document}
