\documentclass[12pt]{article}
\input{macros-course}

\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





\askaboutsolutions









\begin{document}

\ifshowsolutions
  \handout{final}{Final Exam --- Solutions}{December 21, 2001}{\stamp}
\else
  \handout{final}{Final Exam}{December 21, 2001}{\stamp}

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

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{l@{\hskip 3em}l@{\hskip 3em}l@{\hskip 3em}l}
Yu-Han & Christos & Nikos & Ashish \\
\ &&& \\
Thien-Loc & Jaime & Tina & Tong
\end{tabular}
\end{center}

%\noindent Write the hour at which your Thursday tutorial begins \brule{3em}.

\medskip

\begin{closeitemize}
\item This quiz is \textbf{closed book}.  \iffalse There is an Appendix
that includes some standard definitions. The first occurrence of an
item defined in the appendix appears in \textbf{boldface}.\fi

\item There are five (5) problems each worth 20 points.

\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 You may assume any of the results presented in class or in the
  lecture notes.

\item \remove{Show your work, as partial credit will be given.}
\textbf{Be neat and write legibly}.  You will be graded not only on the
correctness of your answer, but also on how clearly you present it.

\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|}
\hline & &\\
Problem & Grade & Grader\\
\hline \hline  & &\\
1 &   & \\ & & \\ \hline  & &\\
2 &   & \\ & & \\ \hline  & &\\
3 &   & \\ & & \\ \hline  & &\\
4 &   & \\ & & \\ \hline  & &\\
5 &   & \\ & &\\
\hline \hline  & &\\
Total &  & \\
& &\\
\hline
\end{tabular}
\end{center}

\newpage
\fi

\iffalse

\begin{verbatim}

%% Quiz 3:
%%-----------
%% Subjects:
%% Summations (series, closed forms, stirling, asymptotic)
%% Counting (sum and product rules, incl-excl, trees, bijections, pigeonhole)
%% (permutations, combinations, binomial theorem and identities, repetitions)
%% Probability (basics, combination of events, conditional)

\end{verbatim}
\fi

\begin{problems}
\problem
Let's analyze an algorithm for generating numbered trees from number
sequences.  We have a graph $G$ of vertices numbered 1 to $n$, a
numbered vertex set $V$ and a sequence $S$ of numbers between 1 and $n$.
Initially $G$ contains no edges, $V=\set{1,2\twodots n}$, and
$S$ has length $n-2$.  Our algorithm proceeds as follows:
\begin{itemize}
\item
If $V$ contains two elements $a, b$, add the edge $e(a, b)$ to $G$ and
terminate.
\item
Otherwise, repeat the following step.  Look at $f$ the first element
of $S$, and $l$ the largest 
element of $V$ which does \emph{not} appear in $S$.
\begin{enumerate}
\item
Add $e(l, f)$ to $G$.
\item
Remove $l$ from $V$.
\item
Remove $f$ from the start of $S$.
\end{enumerate}
\end{itemize}
Let $W$ denote the set of numbers that are in either $V$ or $S$.

\bparts
\ppart
Is this algorithm deterministic or nondeterministic?  No explanation
necessary.

\solnospace{Deterministic}

\ppart
Draw the graphs generated by the following codes:  666666, 72357
\ifshowsolutions
 {}
\else
\vspace*{2in}
\fi

\solnospace{Will draw these in.}

\ppart\label{alg-invs}
Which of the following are candidates for invariants of this
algorithm?  No explanation necessary.
\begin{enumerate}
\item
$G$ has $n-1$ edges. \solnospace{False}
\item
The cardinality $|V|$ of $V$ equals the length $l(S)$ of
$S$. \solnospace{True} 
\item
$|V|-l(S)=2$. \solnospace{True}
\item
Number of edges in $G$ equals $n-|V|$. \solnospace{True}
\item
$G$ contains no cycles. \solnospace{False}
\item
$G$ contains 1 or more cycles. \solnospace{True.  We're being tricky here...}
\item
Every connected component of $G$ has exactly one vertex that is in
$W$. \solnospace{True}
\item
No two vertices of $W$ are connected by a path in $G$. \solnospace{False}
\item
The largest element of $V$ is present in $S$. \solnospace{True}
\end{enumerate}

\ppart\label{alg-term}
Which of the following could be used as a derived variable to show
termination of the algorithm?  No explanation necessary.
\begin{enumerate}
\item
Number of edges in $G$. \solnospace{False}
\item
Number of connected components in $G$. \solnospace{False}
\item
$|V|$. \solnospace{True}
\item
$|V|-l(S)$. \solnospace{False}
\item
$|V|-2l(S)$. \solnospace{False}
\end{enumerate}

\ppart 
Show that the algorithm will terminate.  If using results from parts~(\ref{alg-invs})
and~(\ref{alg-term}), you must prove them.

\solnospace{
We can use $|V|$ as a positive integer valued derived variable to show
termination. At each step, one element is removed from $V$ so $|V|$ is
decremented.
}

\ppart Show that upon termination $G$ has $n-1$ edges and $S$ has
length 0.  If using results from parts~(\ref{alg-invs})
and~(\ref{alg-term}), you must prove them.

\solnospace{
We use the invariant that the number of edges in $G$ equals
$n-|V|$.  This is clearly true at the start and remains true since
every time we add an edge to $G$ we remove an element of $V$.

Another invariant is that $|V|-l(S)=2$.  At each step, we remove
one element from $V$ and one from $S$, so the invariant is
maintained. It is true initially, so must be true at termination.

Just prior to termination, $V$ has 2 members and so $G$ has $n-2$
edges.  Finally, we connect the last two members of $V$ so $G$ has
$n-1$ edges.  $S$ has length $|V|-2=0$.
}

\ppart Show that on termination $G$ is a connected graph on the $n$
vertices.  If using results from parts~(\ref{alg-invs})
and~(\ref{alg-term}), you must prove them.  Conclude that the $G$
consists of a tree at termination.

\solnospace{
We use the invariant that every connected component of $G$ has
exactly one vertex that is in $W$.  Assume this is true.  As we execute
the next step of the algorithm, we add to $G$ the edge $e(l, f)$ with
$l, f\in W$ and $l$ not in $S$.  Subsequently, we remove $l$ from $V$,
so it is no longer in $W$.

Note that $f$ must be in $V$.  Since it was in $S$, it cannot have
been removed from $V$ in any prior step.  This means that $f$ remains
in $W$ even though it was removed from $S$.

Consider the connected components $C_l, C_f$ of $G$ containing $l$ and
$f$.  By invariant hypothesis $l$ must be the unique member
of $W$ in $C_l$, $f$ be the unique member of $W$ in $C_f$.  Upon
addition of $e(l, f)$, $C_l$ and $C_f$ are combined into a single
connected component $C_{fl}$ and $l$ is removed from $W$.  $C_{fl}$
only contains a single member $f$ of $W$ and the invariance condition
is maintained.

This invariant is true at the start (as every vertex of $G$ is a
separate connected component) so it must be true through the running of
the algorithm.  So, it is true at termination.

At termination, $W$ has two members and so $G$ has two connected
components.  When the last two members are connected, $G$ ends up with
exactly one connected component.

$G$ is now a connected graph on $n$ vertices with $n-1$ edges, so it
must be a tree.
}

\ppart
From the above algorithm and its inverse (which we went over in
tutorial) we see that there's a bijection between numbered trees and
length-$(n-2)$ sequences of numbers.  Deduce the number of labeled
trees that can exist on $n$ vertices.

\solnospace{$n^{n-2}$}
\eparts

\ifshowsolutions
 {}
\else
\newpage
\fi

 
\problem

Counting can enable us to prove some relations which are very
difficult to prove analytically.  For example, let's tackle the
frightening looking equation
\begin{eqnarray}\label{reln}
\sum_{i=1}^{n-1}{n-2 \choose i-1}i^{i-2}(n-i)^{n-i-2} = 2n^{n-3}
\end{eqnarray}

\bparts
\ppart\label{simpletreeprob}
From the previous problem, we know that there are exactly $n^{n-2}$ trees on $n$
numbered vertices.  Given a random tree, compute the probability that
it is chosen from a given set $P$ of size $|P|$.

\solnospace{$|P|/n^{n-2}$.}

\ppart\label{expedges}
What is the expected number of edges in a randomly chosen
numbered tree? \solnospace{$n-1$.}

\ppart\label{treeprob1}
Consider the edge between vertices 1-2.  Let $p$ be the probability
that this edge is present in a randomly chosen tree.  Using symmetry
between edges, and your answer to part~\ref{expedges}, what can you
say about $p$?

\solnospace{
There are ${n \choose 2}$ edges totally, and all are equivalent from
the point of view of creating numbered trees.  So by linearity of
expectation, it follows that $p{n \choose 2}=n-1$, or $p=2/n$.
}

\ppart\label{T1}
Let's try to get at this probability another way.  Iff $G$ is a tree
containing 1-2, then removal of the edge 1-2 will split $G$ into two
disjoint trees $T_1$ and $T_2$.  Given that $T_1$ has $i$ vertices,
$T_2$ has $j$ vertices.  How
many different ways are there to construct $T_1$?

\solnospace{
We know $T_1$ contains vertex 1, and does not contain vertex 2.  For
the remaining $i-1$ vertices of $T_1$, we can choose them in ${n-2 \choose
  i-1}$ ways.  For any given selection of vertices there are $i^{i-2}$
ways to permute the tree.  So the answer is
$$
{n-2 \choose i-1}i^{i-2}
$$
}

\ppart\label{T2}
Given a choice for $T_1$, how many ways are there to construct $T_2$?

\solnospace{
The $j=n-i$ vertices of $T_2$ are now determined.  They can be
permuted in $j^{j-2}=(n-i)^{n-i-2}$ ways.
}

\ppart\label{treeprob2}
Combining your answers to part~\ref{T1} and~\ref{T2}, compute the
number of trees containing the edge 1-2.  Use this
and~\ref{simpletreeprob} to deduce a new formula $p'$ for the
probability that a random tree contains this edge.

\solnospace{
$$
p' = \frac{\sum_{i=1}^{n-1}{n-2 \choose
    i-1}i^{i-2}(n-i)^{n-i-2}}{n^n-2}
$$
}

\ppart Equate $p$ and $p'$, and simplify to get equation~\eqnref{reln}

\ppart\label{treevari}
What is the variance $\sigma^2$ of the number of edges in a randomly chosen
numbered tree?

\solnospace{0.  Gotcha.}

\ppart
The variance of an indicator variable with probability $p'$ of
equaling 1 is $p'(1-p')$.  Can we reason exactly as described above to
obtain a new relation:
$$
{n \choose 2}p'(1-p')=\sigma^2
$$
Substituting in $p'$ from part~\ref{treeprob2} and $\sigma^2$ from
part~\ref{treevari}, to get a new relation?  Explain why/why not.

\solnospace{
The variances of the different indicator variables for each edge don't
add up linearly.
}
\eparts

\ifshowsolutions
 {}
\else
\newpage
\fi



\end{problems}
\end{document}

