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

\newcommand\answer[1]{{\bf Answer: {#1}}}
\newcommand{\newgcd}[2]{{\ms{gcd}}(#1, #2)}
%\newcommand{\ms}[1]{%
%        \relax\ifmmode
%                \mathord{\mathcode`\-="702D\it #1\mathcode`\-="2200}%
%        \else
%                $\mathord{\mathcode`\-="702D\it #1\mathcode`\-="2200}$%
%        \fi
%}

\newcommand{\iocode}[2]{\begin{center}\footnotesize
\begin{minipage}[t]{.45\linewidth}
\hbox to\linewidth{}
#1
\end{minipage}
\hspace{.05\linewidth}
\begin{minipage}[t]{.45\linewidth}
\hbox to\linewidth{}
#2
\end{minipage}
\end{center}}

\newcommand{\prcef}[3]{\begin{tabbing}       
XX\=  XX\=XX\=XX\=XX\=  \kill
\protect #1\\
\>Precondition: \+ \+ \\ 
  #2  \-  \- \\ 
\>Effect: \+  \+ \\
  #3 \- \- 
\end{tabbing}} 

\begin{document}
\handout{pfinalsol}{Practice Final Solutions}{December 9, 1997}
\let\comp\circ
\def\blank{\rule[-2pt]{.5in}{.5pt}}
\def\longblank{\rule[-2pt]{2in}{.5pt}}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\problem 

\bparts

\ppart 
A vampire arrives in Boston at day $0$ and starts biting people at day
$1$.  People bitten become vampires themselves.  New vampires bite two
persons on the next day after they were bitten and four persons every
day afterwards.  
Write an expression for the number of vampires in $n$ days for $n \geq 2$, 
assuming the first vampire is a newly made vampire.  
{\em Do not solve the recurrence relation.}

\answer{}

Let $V(n)$ denote the number of vampires on the $n$th day.
We have the initial conditions $V(0) = 1$ and $V(1) = 3$.

The number of vampires on day $n+1$ is the number of vampires on day $n$
plus all the people that were bitten on day $n$.

$$
V(n+1) = V(n) + 2(V(n)-V(n-1)) + 4V(n-1) = 3V(n) +2V(n-1)
$$


\ppart 
Consider the recurrence $T(n)=T(n/2)+T(n/4)+n$ and $T(1)=1$.
Prove that $T(n) \le 4n$, where $n$ is a power of $2$.


\answer{}

The base cases are
$T(1) = 1 < 4$, and $T(2) = T(1) +2 = 3 < 8$.

The inductive step is

$$
T(2n) = T(n) + T(n/2) +2n \le 4n + 2n +2n = 8n \leq 4 \cdot 2n.
$$

The induction is complete.
 

\ppart 
Prove that $T(n)=\Theta(n)$ in the recurrence above.

\answer{}

It suffices to show that $T(n) \geq n$.
Indeed, the base cases are $T(1) = 1 \geq 1$, $T(2) = 3 \geq 2$.

$$
T(2n) = T(n) + T(n/2) + n \geq 2n +n/2 \geq 2n.
$$

The induction is complete.

Parts (b) and (c) establish that  $T(n)=\Theta(n)$.
 
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\bparts

\ppart
Six people communicate via radio frequency with one another. Each pair
of people choose one of {\bf two} available frequencies with which to
communicate.  Show that there is a subset of 3 people who are each
using the identical frequency with which to communicate with others in
the subset.

\answer{}

Each person communicates with five other persons.  By the pigeonhole principle,
this person (say $a$) communicates with another three persons (say $b$,$c$,and $d$)
using the same frequency.
If either of the pairs $(b,c), (b,d), (c,d)$ uses this frequency then we have three persons
using it to communicate with each other and we are done.
If not, then the pairs $(b,c), (b,d), (c,d)$ all use the other frequency, so we are done again.


\ppart
Now suppose there are seventeen people communicating via radio 
frequency with one another. Each pair
of people choose one of {\bf three} available frequencies with which to
communicate.  Show that there is a subset of 3 people who are each
using the identical frequency with which to communicate with others in
the subset.

\answer{}

Now each person communicates with sixteen other people, 
and by pigeonhole uses the same frequency  with at least six of them.
If any pair among these six persons uses that same frequency then we are done.
If not, then these six persons communicate with one another using two 
different frequencies so we are back in part (a) of the problem.


\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_A$ denotes the identity function 
on the set $A$.
For each statement indicate whether it is {\bf T}rue or {\bf F}alse. No
explanation is required.

\def\true{{\bf T}rue:}
\def\false{{\bf F}alse:}

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

\item[\true]
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[\false]
Let $f:A\to B$ and $g:B\to A$. $f\comp g=I_B$ implies $g\comp
f=I_A$.

\item[\true]
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[\false]
Let $f:A\to B$ and $g:B\to C$. $g\comp f$ is a surjection implies both
$f$ and $g$ are surjections.

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

\end{list}

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

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

\item[\true]
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[\false]
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[\false]
The number of length-$3$ paths in an $n$-vertex undirected graph is
       $O(n^2)$.
\item[\false] 
The number of length-$3$ paths in an $n$ vertex tree is $O(n)$
\item[\true]
Reversing the directions of all edges in a directed graph leaves
       the number of simple directed cycles unchanged.
\item[\false]
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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

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

Let $ALL$ be the set of all permutations, 
$BAG$ the set of permutations containing ``bag''
and $DEF$ the permutations containing ``def''.
We want to determine the size of 
$ALL - (BAG\cup DEF)$.

We have $|ALL| = 7!$.
To count the elements of 
$BAG$, notice that the set of permutations containing 
``bag'' is in bijection with the set of permutations of 
$\{a,c,d,f,bag\}$. Therefore $|BAG| = 5!$.
Analogously $|DEF|=5!$ and $|DEF\cap BAG| = 3!$.

By inclusion exclusion:
\[|ALL - (BAG\cup DEF)| = |ALL| - |BAG| - |DEF| + |BAG\cap DEF|
 = 7! - 2\cdot 5! + 3! = 4806\]

\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

\newcommand\ans[1]{\ \ {\bf {#1}}\ \ }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

Consider the following recursive algorithm for coloring a
graph $G$ with natural numbers.  For a vertex $v$, $G-v$ denotes the
graph you get by removing $v$ and all its incident edges from $G$.

\begin{tabbing}
else \= else \= else \= else \= \kill

Color($G$)\\
\> {\bf if} $G$ has 1 vertex $v$\\
\> \> set the color of $v$ to be $0$\\
\> {\bf else}\\
\> \> choose a vertex $v$ of $G$\\
\> \> Color($G-v$)\\
\> \> set the color of $v$ to be the minimum $n \in \nat$ for
which no neighbor of $G$ has color $n$\\
\end{tabbing}
Prove that this algorithm legally colors $G$ with a number of colors
no more than 1 plus the maximum degree of a vertex in $G$.

\answer{}

We perform induction on the number of vertices of $G$.

$P(n) = \{$ If $G$ has $n$ vertices, Color(G) legally colors $G$
with no more than one plus the maximum degree of a vertex in $G$ \}


BASE CASE: $n=1$, in which case the graph is colored with one color and the
statement is true.

INDUCTIVE STEP:
Consider now a graph with $n+1$ vertices.  Then $G-v$ has $n$ vertices and the
algorithm colors it legally with at most $1+d$ colors, 
where $d$ is the maximum degree
of $G-v$. 

If $v$ is connected to some maximum degree vertex, then the maximum
degree of $G$ is $d+1$, and since $v$ is colored with at most one new color,
the total number of colors for $G$ is at most $d+2 = 1+$maximum degree of $G$.

If $v$ is not connected to some maximum degree vertex, then we can distinguish
the following cases:

a) Either $v$ has degree at least $d+1$, in which case the maximum degree of 
$G$ is at least $d+1$, and at most $d+2$ colors are required, or

b) $v$ has degree at most $d$, which means that it can be colored with one of
$d+1$ colors.  Therefore, the maximum number of colors remains $d+1$.


  
\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

For a certain test for a newly discovered virus, called JABOLA, it is
known that $99\%$ of the people carrying the virus will test positive,
whereas only $1\%$ of the people not carrying the virus will test
positive. Suppose $0.5\%$ of the population carries the JABOLA virus.
Given that a person picked at random tests positive, what is the
conditional probability that this person carries the JABOLA virus?

\answer{}
Let $T = \{\text{test is positive} \}$, $V = \{\text{person has the JABOLA virus}\}$.
We are given that $P(T|V) = 0.99$, $P(T|\bar{V}) = 0.01$ and $P(V) = 0.005$.

$$
P(V|T) = \frac{P(T|V)P(V)}{P(T)} = \frac{P(T|V)P(V)}{P(T|V)P(V)+P(T|\bar{V})P(\bar{V})}
$$

The above expression evaluates to $0.3322$.

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

\answer{} There are $100\choose 7$ ways to pick tagged trout, $n-100 \choose 93$ to pick untagged trout, and $n \choose 100$ ways to pick 100 trout out of the lake. Since all trout are equally likely to be caught, the probability of catching 7 tagged is
\[
{100 \choose 7}{n-100 \choose 93} \over
{n \choose 100}{.}
\]

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

\answer{} The probability of catching a tagged trout is $p=100/n$. The probability of catching 7 tagged and 93 untagged in a given sequence is $p^7(1-p)^{93}$. Thus the probability of catching 7 tagged trout (in any sequence) is
\[
{100 \choose 7}\left({100\over n}\right)^7\left(1-{100\over n}\right)^{93}{.}
\]

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

\answer{}
This is equivalent to placing 13 balls (corresponding to each card in
a hand) to 4 bins (corresponding to each suit). Thus the number of
distributions is
\[
{\rm BP}(13,4) = {13 + 4 - 1 \choose 4 - 1} = 560{.}
\]

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

\answer{}
By using the same correspondence as in part (a), the number of
distributions is
\[
{\rm BP1}(13,4) = {13-1 \choose 4-1} = 220{.}
\]

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Suppose the entries $a,b,c,d$ of a $2\times 2$ matrix 

$$
M=
\begin{pmatrix}
a & b\\ c & d \end{pmatrix}\quad
$$

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)$?

Using linearity of expectation
\[E(X) = E(ad+bc) = E(ad) - E(bc) = 0\]
because $ad$ and $bc$ are identically distributed.

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

Using linearity of expectation and the rule 
$E(XY)=E(X)E(Y)$ for independent random variables
we have
\begin{eqnarray*}
E(X|b=1) &=& E(ad|b=1)  - E(bc|b=1) \\
  &=& E(ad) - E(c) \\
  &=& E(a)E(d) - E(c) \\
  &=& 2\cdot 2 - 2 = 2
\end{eqnarray*}

\ppart What is $Var(X)$?

\begin{eqnarray*}
 Var(X) &=& E(X^2) - E(X)^2 \\
 &=& E(X^2)\\
 &=& E((ad-bc)^2) \\
 &=& E(a^2d^2+b^2c^2-2abcd) \\
 &=& E(a^2)E(d^2) + E(b^2)E(c^2) - 2E(a)E(b)E(c)E(d) \\
 &=& 6\cdot 6 + 6\cdot 6 - 2\cdot 2^4 = 40
\end{eqnarray*}

\eparts

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

We consider an algorithm based on a given rooted, undirected tree,
oriented with the root on the top.  Every node in the tree has an
associated $\ms{value}$ variable.  Initially, the $\ms{value}$
variables of the leaves contain natural number input values, and the
$\ms{value}$ variables of the root and other internal nodes contain a
special ``undefined'' value $\bot$.  The algorithm is supposed to end up
with the root's $\ms{value}$ variable containing the sum of all the
$\ms{value}$s of all the leaves.  This is accomplished by propagating
summarized $\ms{value}$ information up the tree structure.

%This algorithm is described precisely by the following state machine.
%This machine assumes a fixed undirected tree $T = (V,E)$, rooted at
%node $r$.
%The state components are:

%for each $v \in V$: \\
%\hspace*{4mm} $\ms{value}(v) \in \naturals \cup \{ \bot \}$; 
%initially $\ms{value}(v)\in \naturals$ if $v$ is a leaf, and 
%$\ms{value}(v)=\bot$ if $v$ is an internal node.

%The transitions are:

%\iocode{
%\prcef{$\ms{summarize}(v)$, $v$ an internal node}
%{%Precondition:
%  $\ms{value}(v) = \bot$ \\
%  for every $w \in \ms{children}(v)$ \\
%  \hspace{2mm} $\ms{value}(w) \in \naturals$}
%{%Effect:
%  $\ms{value}(v) := \sum_{w \in \ms{children}(v)} \ms{value}(w)$}
%}{}

{\bf If}
\hspace{.2in}  $\ms{value}(v) = \bot$ 

\hspace{.2in} and for every $w \in \ms{children}(v)$, 
\hspace{2mm} $\ms{value}(w) \in \naturals$

{\bf Then}
\hspace{.2in}  $\ms{value}(v) := \sum_{w \in \ms{children}(v)} \ms{value}(w)$


The property we are interested in is that $\ms{value}(r)$ for the root
$r$, if it ever gets defined, is equal to the sum of the $\ms{value}$s
of all the leaves.  Formally: 

Inv1: If $\ms{value}(r) \in \naturals$, where $r$ is the root, then
$\ms{value}(r) =
\sum_{l \in \ms{leaves}} \ms{value}(l)$.


\bparts

\ppart
Describe a state machine for this algorithm.

\answer{}

This algorithm is described precisely by the following state machine.
This machine assumes a fixed undirected tree $T = (V,E)$, rooted at
node $r$.
The state components are:

for each $v \in V$: \\
\hspace*{4mm} $\ms{value}(v) \in \naturals \cup \{ \bot \}$; 

Initially $\ms{value}(v)\in \naturals$ if $v$ is a leaf, and 
$\ms{value}(v)=\bot$ if $v$ is an internal node.

The state transitions are described by the algorithm.

\ppart
State and prove a strengthened version of Inv1, which can be proved by
induction.

\eparts

\answer{}

Inv2:

If $v$ is any node of $T$ and $\ms{value}(v) \in \naturals$,
then $\ms{value}(v)$ is the sum of the $\ms{value}$ of all the leaves
that are descendants of $v$.

%Why is Inv2 true in the base case?

BASE CASE:  For internal nodes, $\ms{value}(v) \not \in \naturals$, so Inv2
is vacuously true.  For leaves, the only leaf below $v$ is $v$ itself,
so $\ms{value}(v)$ alone gives the correct sum.

%Why does the inductive step hold?

INDUCTIVE STEP:  When the algorithm is performed, the sums of all the
$\ms{value}$s of $v$'s children are added.  The inductive hypothesis
says that each of these $\ms{value}$s is the sum of the leaves below
the corresponding child.  Adding them all up gives the sum of all the
leaves below $v$.

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\bparts

\ppart
At Marilyn's Casino, a new gambling game has been introduced.  
The game features 3 fair mutually independent 6-sided dice.  To play, the
contestant picks a number in the interval $[1,6]$.  The contestant
wins $\$1$ if his/her number comes up on one or more of the dice and loses
\$1 otherwise.  This game has proved to be very popular with the
gamblers such as Bobo who is a regular. Your job is to figure
out the probability of winning the game.

\answer{}

$\Pr(\mbox{WIN}) = 1 - (5/6)^3 = {91 \over 216}$

\ppart
In an effort to attract even more gamblers to her casino, Marilyn is
thinking about a variation of the game in which the bettor also picks
a different second chance number and the bettor wins if the first pick comes up
at least once or the second pick comes up at least twice. Compute the
probability of winning this game.

\answer{}

The probability  that the second chance number comes up twice is

$\Pr(\mbox{2nd chance}) = {3 \choose 2}(1/6)^2 (5/6) = {15 \over 216}$

The probability that the first number comes up once {\em and} the second
chance number comes up twice is ${3 \over 216}$.

By inclusion/exclusion the probability of winning is

$\Pr(\mbox{WIN}) = {91 \over 216} + {15 \over 216} - { 3 \over 216} = 
{103 \over 216}$

\eparts

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

What is your expected return in each of the following games? You may
assume the events are independent in each part.

\bparts

\ppart
 You get to roll six ordinary six-sided dice.  You win the number of
dollars equal to the total number of spots that appear on all the dice.

\answer{}

The expected return from a single dice is $7/2$. By linearity of 
expectation the total expected return is $6{7 \over 2} = 21$.

\ppart
 You roll one ordinary die.  You win a number of dollars that is
equal to six times the number of spots. 

\answer{}

Again by linearity of expectation, the expected return is 21.

\ppart
 You toss a fair coin six times.  For each time it comes up heads,
you toss an ordinary six-sided die.  You win the number of dollars
equal to the total number of spots that appear on all the dice.

\answer{}

Let $N$ be the number of heads in the six coin tosses, $X_i$ be the number
of spots in the $i$th die toss. The expected return is
$\sum_{i=1}^N X_i$

$N$ is binomial and it's mean is $3$, while each $X_i$ has mean $7/2$,
so by Wald's identity, the expected return is ${21 \over 2}$.

\ppart
 You toss a fair coin repeatedly, until it comes up ``tails'' for the
first time.
(This could involve infinitely many tosses, if ``tails'' never comes up.)
For each time the coin comes up heads, you toss an ordinary six-sided
die.  You win the number of dollars equal to the total number of spots
that appear on all the dice.

\answer{}

Again we have $\sum_{i=1}^N X_i$, but now $N$ is geometric and has mean 2.
Therefore, by Wald's identity the expected return is $2 {7 \over 2} = 7$.

\ppart
 You roll two six-sided dice.  You win the product of the number of
spots that appear on the two dice.

\answer{}

$E[X]^2 = {49 \over 4}$

\ppart
 You roll one ordinary die.  You win a number of dollars that is
the square of the number of spots.

\answer{}

$E[X^2] = {1+4+9+16+25+36 \over 6} = {91 \over 6}$

\eparts

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

There is a newly developed test called EQ ({\em Emotional Quotient}),
that is used to decide whether or not you will succeed in life.
EQ is expressed as a nonnegative integer.  
The average EQ over all humans is~1000.  

\bparts

\ppart
Knowing only the average EQ, find an upper bound for 
the fraction of humans that have EQ$\geq 1500$?

\answer{}

We use Markov's inequality $\Pr(X \geq cE[X]) \leq 1/c$,
with $c = 1.5$, to obtain the upper bound $2/3$.

\ppart
Assuming that the standard deviation of 
EQ is~100, what fraction of humans can have EQ$\geq 1500$?

\answer{}

We use Chebychev's inequality 
$\Pr(X \geq E[X] + c \sigma_X) \leq {1 \over 1+c^2}$
with $c = 5$ to get an upper bound of ${1 \over 26}$

\eparts


\end{problems}
\end{document}
