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

\begin{document}
\handout{final}{Final Exam}{May 24, 1996}
\let\comp\circ
\def\blank{\rule[-2pt]{.5in}{.5pt}}
\def\longblank{\rule[-2pt]{2in}{.5pt}}

This is an OPEN BOOK Final: you may refer to books, handouts, or your
own course notes.  (Calculators are not allowed.)  You may use in your
problem solutions any of the mathematical results given in lectures,
recitations, or the course text.  There are twelve problems of roughly
equal weight to complete within three hours.

Write all solutions in the exam book. You may use the back of the
pages if you need more space.

Good luck!

\vspace{0.5in}
{\large \bf Name: \rule[-2pt]{4in}{.5pt}}
\vspace{0.5in}

\renewcommand{\arraystretch}{.5}
\begin{center}
{\small
\begin{tabular}{|c|c|}
\hline
& \hspace*{1in}\\
Problem&Grade\\
& \\
\hline
\hline
& \\
1 &   \\& \\\hline & \\
2 &   \\& \\\hline& \\
3 &   \\& \\\hline& \\
4 &   \\& \\\hline& \\
5 &   \\& \\\hline& \\
6 &   \\& \\\hline& \\
7 &   \\& \\\hline& \\
8 &   \\& \\\hline& \\
9 &   \\& \\\hline& \\
10 &   \\& \\\hline& \\
11 &   \\& \\\hline& \\
12 &   \\& \\
\hline
\hline
& \\
Total & \\
& \\
\hline
\end{tabular}
}
\end{center}

\newpage
\begin{problems}

\problem
Let $A$ be a set and $R$ be a binary relation on $A$.  For each of the
statements in the box on the left below, indicate the number of the
formula in the box on the right expressing that property.  (Recall that
the {\em composite} of two binary relations $R$ and $S$, written $S\circ
R$, is the relation $\{(a,c)\mid \mbox{there exists some $b$ such that
$(a,b)\in R$ and $(b,c)\in S$}\}$.  $R^T$ is the {\em transpose} of $R$,
i.e., $R^T=\{(a,b)\mid (b,a)\in R\}$, and $I$ denotes the {\em identity}
relation on $A$, i.e., $I=\{(a,a)\mid a\in A\}$.)

\renewcommand{\arraystretch}{1.2}
\begin{tabular}{|c|l|c|}\hline
a. & $R$ is transitive & \mbox{ \hspace{.2in}   } \\ \hline
b. & $R$ is antisymmetric & \\ \hline
c. & $R$ is reflexive & \\ \hline
d. & $R$ is symmetric & \\ \hline
e. & $R$ is a bijection & \\ \hline
f. & $R$ is an equivalence relation & \\ \hline
g. & $R$ is a partial order & \\ \hline
\end{tabular}
\qquad
$\begin{array}{|cl|}\hline
1. & R = R^T \\ 
2. & R\circ R \subseteq R \\
3. & R\cap R^T \subseteq I \\
4. & R\cap R^T \subseteq I \subseteq R\circ R \subseteq R \\ 
5. & I\subseteq R \\ 
6. & R\circ R^T = R^T\circ R = I \\
7. & I \subseteq R\circ R \subseteq R \subseteq R^T\cap R\\ 
\hline
\end{array}$
\problem
\bparts
\ppart
Consider the set of polynomials with {\bf integer} coefficients.  We claim
this set is countable.  In fact, the proof is very similar to Problem 5 on
Problem Set 4 (see Appendix).  However, we need to choose a new definition
of the norm.  In particular, we wish to maintain the property that the
number of polynomials that have norm $k$ is finite for any $k$.  Which of
the following definitions of norm are appropriate?  (There may be more
than one correct answer; list them all.)  We let $d$ denote the degree of
the polynomial and $a_0, a_1, a_2, \ldots, a_d$ denote the coefficients.
\[
\begin{array}{ll}
(i) &\max(d, a_0) \\
(ii) &\max (d, a_0, a_1, a_2, \ldots, a_d) \\
(iii)& \max (d,|a_0|, |a_1|, |a_2|, \ldots, |a_d|) \\
(iv) &\max (|a_0|, |a_1|, |a_2|, \ldots, |a_d| ) \\
(v) &\max (d, a_0^2, a_1^2, a_2^2, \ldots, a_d^2) 
\end{array}
\]

Answer: \longblank

\ppart
A real number is called {\em algebraic} if and only if it is the root of a
non-zero polynomial with integer coefficients.  You may recall that every
nonzero polynomial has a finite number (possibly zero) of real roots.  Are
the algebraic numbers countable or uncountable?

Answer: \longblank

\ppart 
Some numbers (such as $\pi$ or $e$) cannot be expressed as a root of a
polynomial with integer coefficients.  These numbers are called the
transcendental numbers.  Is the set of transcendental numbers countable or
uncountable?

Answer: \longblank

\eparts

\newpage
\problem
In this problem, $A$, $B$ and $C$ denote arbitrary sets. $f$ and $g$ are
functions as specified in each part and $I$ denotes the identity function.
For each statement indicate whether it is {\bf T}rue or {\bf F}alse. No
explanation is required.

\begin{list}{{\bf T\ \ F\ \ \ }}{\setlength{\leftmargin}{40pt}%
        \setlength{\labelwidth}{\leftmargin}%
}

\item
There exists an injection (one-to-one) $f:A\to B$ if and only if there
exists a surjection (onto) $g:B\to A$.

\item
Let $f:A\to B$ and $g:B\to A$. $f\comp g=I$ implies $g\comp
f=I$.

\item
Let $f:A\to B$ and $g:B\to C$. If both $f$ and $g$ are injections,
then $g\comp f$ is an injection.

\item
Let $f:A\to B$ and $g:B\to C$. $g\comp f$ is a surjection implies both
$f$ and $g$ are surjections.

\item
Let $f:A\to B$ be an injection. If $|B|\leq |A|$, then $f$ is a
bijection.

\end{list}

\problem Answer {\bf T} or {\bf F}:
%\mbox{ }

\begin{list}{{\bf T\ \ F\ \ \ }}{\setlength{\leftmargin}{40pt}%
        \setlength{\labelwidth}{\leftmargin}%
}
\item 
The mapping $f_a:Z_p \rightarrow Z_p$ defined by
\[ f_a(x) = ax \mod{p}\]
is a bijection for any nonzero $a\in Z_p$, when $p$ is prime.
\item
For all $a,b$ in $\naturals$, $\gcd(a^2b,ab^2) = ab$.
\item
If $a^{-1}\mod{b}$ exists, then
so does $b^{-1} \mod{a}$.
\item
Let $\lambda(n)$ denote the number of distinct prime factors
of $n$.  Then $\lambda(n) = \Omega(\mbox{lg lg } n)$.
\end{list}

\problem %\mbox{ }
Answer {\bf T} or {\bf F}:

\begin{list}{{\bf T\ \ F\ \ \ }}{\setlength{\leftmargin}{40pt}%
        \setlength{\labelwidth}{\leftmargin}%
}

\item Adding $k$ edges to an undirected graph increases its chromatic
       number (the number of colors needed to color the vertices)
       by at most $k$.
\item The number of shortest paths in an $n$-vertex undirected graph is
       $O(n^2)$. (Note: there may be more than one shortest path between
       two vertices.)
\item Reversing the directions of all edges in a directed graph leaves
       the number of simple directed cycles unchanged.
\item If an undirected graph has the degree of every vertex divisible
       by a prime $p$, then $p$ must evenly divide the number of edges.
\end{list}


\renewenvironment{proof}{\par{\noindent\em Proof.}\hspace{1em}\setlength{\parindent}{0pt}}{\qed}

\newcommand{\binom}[2]{{#1 \choose #2}}
\newcommand{\Prob}[1]{{\rm Pr}(#1)}
\def\medblank{\rule[-2pt]{1in}{.5pt}}

\newpage
\problem

Given events $A_1,\cdots, A_n$, let $N$ be the random variable equal to
total number of these events which occur in a single trial.  Let $B$ be
the event that none of the $A_{i}$ occurs.  When the events are
{\em independent}, we can prove that the likelihood of $B$ decreases
exponentially with the expected value of $N$, namely
\[
\Prob{B} \leq e^{-E(N)}.
\]
Here is a proof---with justifications for many of the lines omitted.
\begin{proof}
\[
\begin{array}{rcl@{\hspace{0.25in}}l}
B &=& \overline{A_1} \cap \cdots \cap \overline{A_n} & \mbox{by }(a)\medblank\mbox{. Hence,}\\
\Prob{B} &=& \displaystyle \Prob{\overline{A_1} \cap \cdots \cap \overline{A_n}}\\
&=& \displaystyle \prod_{i=1}^{n} \Prob{\overline{A_i}} & \mbox{by }(b)\medblank\\
&=& \displaystyle \prod_{i=1}^n (1- \Prob{A_i}) & \mbox{by }(c)\medblank\\
&\leq& \displaystyle \prod_{i=1}^n e^{-\Prob{A_i}} & \mbox{by }(d)\medblank\\
&=& \displaystyle e^{-\sum_{i=1}^n \Prob{A_i}} & \mbox{by }(e)\medblank\\
&=& \displaystyle e^{-E(N)} & \mbox{by }(f)\medblank{.}
\end{array}
\]
\end{proof}

Match the correct justifications from the following list with the places
(a)--(f) where they are needed in the proof.

\begin{enumerate}
\item the product rule for probabilities of independent events
\item the product rule for expectations of independent events
\item the product rule for probabilities of disjoint events
\item the sum rule for probabilities of independent events
\item the sum rule for expectations of independent events
\item the sum rule for probabilities of disjoint events
\item the sum rule for expectations of indicator variables
\item definition
\item Chernoff's bound for a sum of index variables
\item inequality $e^x \ge 1+x$
\item the bounds on the tail of a binomial distribution
\item arithmetic rules for exponents
\item arithmetic rules for $\log_{e}$
\end{enumerate}

\problem For each of the following pairs of functions $f(n)$ and $g(n)$,
fill in the blank with $o$, $O$, $\omega$, $\Omega$, and $\Theta$
depending on whether $f(n)=o(g(n))$, $f(n)=O(g(n))$, $f(n)=\omega(g(n))$,
$f(n)=\Omega(g(n))$, or $f(n)=\Theta(g(n))$.  If there is more than one
relation between $f(n)$ and $g(n)$, write the strongest one.  Suboptimal
answers will get partial credit but incorrect answers will be penalized,
so do not guess unless you are reasonably sure.  As usual, $\lg n$ denotes
logarithm to the base~2, and $\lg^2 n$ denotes $(\lg n)^2$.

\[
\begin{array}{rcl}
 4^{\lg n}       & = & \blank  (n^{1.5 })\\
\vspace*{0.05in}\\ 
 (2n)!              & = & \blank (2^n(n!)) \\
\vspace*{0.05in}\\
  n^{(\lg^2 n)}   & = & \blank \left(2^{\lg^3 n}\right) \\
\vspace*{0.05in}\\
\displaystyle {2n \choose n}
                & = & \blank (n^n)
\vspace*{0.15in}\\
\displaystyle \frac{n^4+n^2+2}{n^2+1}
                & = & \blank \left( \displaystyle \sum_{i=1}^n i \right)
\end{array}
\]
\problem
We wish to prove by induction on $n$ that the recurrence
\[
T(n) = T(n/2) + T(n/4) + n
\]
has an asymptotic growth rate of $O(n)$.

Which of the following induction hypothesis will provide a correct
proof? (List all correct answers; more than one may be correct.)

\[
\begin{array}{ll}
(i) & T(n) \leq 2n \\
(ii) & T(n) \leq 4n^2 \\
(iii) & T(n) \leq 10n \\
(iv) & T(n) \leq 4n \\
(v) & T(n) \leq 3n+10
\end{array}
\]

Answer: \longblank


\newpage
\problem 
A lake contains $n$ trout.  100 of them are caught, tagged and returned to
the lake.  Later another 100 trout are caught, selected independently from
the first 100.

\bparts \ppart Assume that the second 100 trout are selected without
replacement.  Write an expression (in $n$) for the exact probability that
these trout are found to contain exactly 7 tagged ones.

\vspace{2in}


\ppart Now consider selecting the second 100 trout with replacement. That
is, you repeat 100 times the following steps: select at random a trout in
the lake, check if the trout is tagged and return it to the lake before
selecting a new trout.

What is the probability that exactly 7 of the selected trout are
tagged?

\vspace{2in}

\ppart What is the best way to come up with an estimate of the expression
found in part (b) as $n$ becomes large?  Select your answer from the
following:
\begin{enumerate}
 \item use Markov inequality
 \item use the bound on the tail of the binomial distribution
 \item use the central limit theorem
 \item use Chebyshev inequality
 \item use Poisson approximation
\end{enumerate}

Answer: \longblank
\eparts

\newpage
\problem A bridge hand consists of 13 cards.  The {\em suit-distribution}
of a hand is the number of cards in each suit.  For example, one possible
suit-distribution is 4 spades, 3 hearts, 3 diamonds, and 3 clubs.  \bparts
\ppart How many different suit-distributions are there?

\vspace{2in}

\ppart
How many different suit-distributions are there assuming that you get at
least one card in each suit?

\vspace{2in}

\ppart Suppose the actual suits don't matter.  The {\em card-distribution}
is specified by the {\em set} of numbers of each suit.  In the previous
example, the card-distribution would be $\{4, 3, 3, 3\}$.  How many
card-distributions are possible for a bridge hand?  (You need not give a
numerical answer, but may use notation from Handout 32 -- Notes on
Counting.)

\vspace{2in}

\eparts



\problem
Suppose the entries $a,b,c,d$ of a $2\times 2$ matrix 
\[
	M=\left[\matrix{a&b\cr c&d\cr}\right]
\]
are chosen independently at random according to the uniform
distribution on $\{0,1,2,3,4\}$.  Let $X = \det(M) = ad-bc$.
\bparts
\ppart What is $E(X)$?

\vspace{2in}

\ppart What is $E(X\mid b = 1)$?

\vspace{2in}
\ppart What is $Var(X)$?

\vspace{2in}
\eparts

\newpage
\problem 

Find the number of permutations of the letters 
$\{a,b,c,d,e,f,g\}$ that do not contain 
``bag'' or ``def''.

\vspace{4in}

\end{problems}

\newpage
{\bf \large Appendix}

\newcommand{\seq}[1]{\mbox{seq}(#1)}
\newcommand{\tuple}[1]{\langle{#1}\rangle}
\let\Union\bigcup

\noindent {Problem 5 from Problem Set 4.}
% \problem %
Let $A$ be a set. Define the set $\seq{A}$ to be the set of all
finite tuples of one or more elements in $A$.  Namely,
\[\seq{A} = \Union_{n>0}{\underbrace{A\times\cdots\times A}_n}.
\]
We say a set $S$ is {\em countable} iff there is an injection from $S$
to $\nats$.  Prove that $\seq{\nats}$ is countable.

Hint: Define the {\em norm} of any tuple $\tuple{n_1,\dots,n_k} \in
\seq{\nats}$ to be $\max{\{k, n_1, \dots, n_k\}}$.  Observe that for any
$k>0$, there are only finitely many tuples with norm $k$.

\begin{proof}
Define the {\em norm} of any tuple $\tuple{n_1,\dots,n_k} \in
\seq{\nats}$ to be $\max{\{k, n_1, \dots, n_k\}}$.  
Note that if a tuple $t$ has norm $k$
then $t$ has at most $k$ elements
and each element of $t$ is a number between $1$ and $k$ (inclusive).
Thus for any $k > 0$ there are at most $s_k=k^{k+1}$ tuples with
norm $k$.

Let $N(k) = \{ t \mid t \mbox{ is a tuple with norm } k\}$.
Since each $N(k)$ has at most $s_k$ elements
we can find injective functions 
$f_1$ from $N(1)$ to $\{1,\ldots,s_1-1\}$,
$f_2$ from  $N(2)$ to $\{s_1,\ldots,s_1+s_2-1\}$
and in general 
$f_n$ from $N(n)$ to $\{\sum_{i=1}^{n-1}s_i,\ldots,\sum_{i=1}^ns_i-1\}$.

Since $\{N(n)\}_{n>0}$ is a partition of $\seq{\nats}$,
we can define a function $f$ from $\seq{\nats}$
to $\nats$ by $f(t)=f_n(t)$
where $n$ is the norm of $t$.
Since $f$ maps different $N(n)$'s to disjoint 
subsets of the integers, and each function $f_n$
is injective on its domain,
then $f$ is an injection on the set of all integers.

\end{proof}

\newpage
{\bf \large Blank Page}

\end{document}
