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

\def\longblank{\rule[-2pt]{2in}{.5pt}}

\begin{document}
\handout{conflict-final}{Conflict Final Exam}{May 22, 1996}

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.

Please do not discuss the problems with other sudents in the class
before the regular final exam which is scheduled for Friday morning.

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

Good luck!

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

\bigskip

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

\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@{\hspace{0.4in}}|}\hline
a. & $R$ is a transitive relation & \\ \hline
b. & $R$ is antisymmetric & \\ \hline
c. & $R$ is reflexive & \\ \hline
d. & $R$ is symmetric & \\ \hline
e. & $R$ is a function & \\ \hline
f. & $R$ is an equivalence relation & \\ \hline
g. & $R$ is a partial order & \\ \hline
\end{tabular}
\qquad
$\begin{array}{|cl|}\hline
1. & I\subseteq R \\ 
2. & R = R^T \\ 
3. & I \subseteq R\circ R \subseteq R \subseteq R^T\cap R\\ 
4. & R\cap R^T \subseteq I \subseteq R\circ R \subseteq R \\ 
5. & R\circ R \subseteq R \\
6. & R\circ R^T \subseteq I\subseteq R^T\circ R \\
7. & R\cap R^T \subseteq I \\
\hline
\end{array}$

\problem
\let\comp\circ

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 true or
false. No explanation is required.

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

\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
If for all $f:A\to B$ and $g:B\to A$, $f\comp g=I$ implies
$g\comp f=I$, then $A$ and $B$ are finite.

\item
If $f:A\to B$ is an injection (one-to-one), then there is a $g:B\to A$, such
that $f\comp g=I$.

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

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

\end{list}

\newpage
\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$.

\def\blank{\rule[-2pt]{.5in}{.5pt}}
\[
\begin{array}{rcl}
 8^{\lg n}       & = & \blank (n^{7.5 })\\
\vspace*{0.05in}\\ 
 n^n(n!)         & = & \blank (2n)! \\
\vspace*{0.05in}\\
 2^{\lg^3 n}     & = & \blank n(\lg^2 n) \\
\vspace*{0.05in}\\
 n^{375}		 & = & \blank {n \choose 375}
\end{array}
\]

\problem
We wish to prove by induction on $n$ that the recurrence
\[
T(n) = 2T(n/3) + 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 13n \\
(ii) & T(n) \leq 4n^2 \\
(iii) & T(n) \leq 10n \\
(iv) & T(n) \leq 4n \\
(v) & T(n) = O(n) \\
(vi) & T(n) \leq 10n+10
\end{array}
\]

Answer: \longblank

\newpage
\problem
Prove that a countable union of countable sets is countable. In other
words, let $A_1,A_2,\dots$ be countable sets. Let $A = \bigcup_{n\geq
1}A_n$. Show that $A$ is countable.

\newpage
\problem 

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

\newpage
\problem
Let $G$ be an undirected graph with $k$ nodes. Prove that the number
of colorings of $G$ with $n$ colors is $\Theta(n^k)$.

\newpage
\problem
Each of $n$ people independently picks a number from $\{1,2,3,\ldots,n\}$
according to a uniform distribution.  Let $X$ denote the product
of the number selected.
\bparts
\ppart
What is $E(X)$?
\vspace{2in}
\ppart
How does your answer in part (a) compare to $n!$\ ?
(Use asymptotic notation.)
\vspace{2in}
\ppart
What is $Var(X)$?  (Hint:  $\displaystyle \sum_{i=1}^{n}i^2 = \frac{n(n+1)(2n+1)}{6}$)
\eparts

\newpage
\problem

Solve
\begin{eqnarray*}
3x+5y &=& 7 \\
4x+2y &=& 3
\end{eqnarray*}
in mod 11.

\newpage
\problem
({\em Two-ball roulette}\,) At a casino, a two-ball version of
roulette is played. Players place their bets as in the regular
roulette, and collect winnings for each of the balls, e.g. if a player
bets on red, and only one ball lands on red he breaks even; if both
balls land on red he wins his bet, and if none of the balls lands on
red he loses his bet.

There are 18 red, 18 black and two green numbers in roulette. We
assume that in the two-ball roulette the two balls cannot land on the
same number, but they are equally likely to land on any pair of
distinct numbers. For simplicity assume players only bet on red or
black.

\bparts
\ppart
What is the probability of winning, losing and breaking even?
\vspace{2in}

\ppart
What is the expected winning on a single \$100 bet on red?
\vspace{2in}

\ppart
Is the two-ball roulette more or less profitable for the casino than
the standard roulette?

\eparts

\newpage
\problem
Consider the 5 letter words over an alphabet of 26 letters.

\bparts
\ppart
How many different 5 letter words (not necessarily meaningful) are there?
\vspace{3in}

\ppart
We now consider two words to be equivalent if they are permutations of
each other, e.g. ``asdfa'' $\equiv$ ``dsfaa''. How many such
equivalence classes of words are there?

\eparts

\newpage
\problem
Let $S=\{ 1,2,3,\dots,200 \}$. Prove that for any set $A\subset S$ of
101 numbers, there are two numbers $a,b\in A$ such that $a|b$.

\end{problems}

\end{document}
