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

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}
\def\medblank{\rule[-2pt]{1in}{.5pt}}
\def\relz{\mathbin{\, \rho \,}}

\newcommand{\emptybox}[3][]{%
\begin{center}
    \leavevmode\fbox{%
        \vbox to #3{%
            \vfil
            \hbox to #2 {\hfil#1\hfil}%
            \vfil
        }%
    }%
\end{center}
}

\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

\newcommand{\eqdef}{\mathbin{::=}}

\newcommand{\smallspace}{\ifshowsolutions\else\vspace{1in}\fi}
\newcommand{\mediumspace}{\ifshowsolutions\else\vspace{3in}\fi}
\newcommand{\largespace}{\ifshowsolutions\else\vspace{4in}\fi}
\newcommand{\nextproblem}{\newpage}


\askaboutsolutions

\ifshowsolutions
  \newcommand{\reading}[1]{}
%
  \newcommand{\handoutlabel}{pfinalsol}
  \newcommand{\handouttitle}{Practice Final Quiz (Fall '99) Solutions}
  \newcommand{\handoutdate}{May 11, 2000}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else 
  \newcommand{\reading}[1]{}
  \newcommand{\handoutlabel}{pfinal}
  \newcommand{\handouttitle}{Practice Final Quiz (Fall '99)}
  \newcommand{\handoutdate}{May 7, 2000}
  \newcommand{\duedate}{Never}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\fi

%\renewcommand{\solution}[1]{\ifshowsolutions\par\textbf{Solution.} #1\fi}
%\newcommand{\ksource}[1]{\ifshowsolutions\par\textsc{Source: #1}\fi}

\renewcommand{\solution}[1]{%
  \ifshowsolutions %
  \textbf{Solution.} \par %
  #1
  \mbox{} \\
  \mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
  \raisebox{-0.25\baselineskip}{$\square$}%
  \hspace*{1ex}\ignorespaces\hrulefill%
  \nopagebreak%
  \fi}

\addtolength{\topmargin}{-.2in}
\setlength{\textheight}{9in}

\newcommand{\pts}[1]{\relax[#1 points]\enskip\ignorespaces}
\newcommand{\onept}{\relax[1 point]\enskip\ignorespaces}

\setcounter{page}{0}

\begin{document}

\titlebar 

\begin{problems}

\problem [18 points] \textbf{Injections and Cardinality.}

\bparts

\ppart 

[8 points] Let $f:D \to D$ be a function from some nonempty set $D$ to itself.
In the following propositions, $x$ and $y$ are variables ranging over $D$,
and $g$ is a variable ranging over functions from $D$ to $D$.  Circle all
of the propositions that are equivalent to the proposition that $f$ is an
\emph{injection}:

\begin{enumerate}
\item $x =y \vee f(x) \neq f(y)$
\item $x =y \implies f(x) = f(y)$
\item $x \neq y \implies f(x) \neq f(y)$
\item $f(x) =f(y) \implies x = y$
%\item $\forall x \forall y(f(x) \neq f(y))$
\item $\neg[\exists x\exists y(x \neq y \wedge f(x)= f(y))$
\item $\neg[\exists z \forall x(f(x) \neq z)$
\item $\exists g \forall x (g(f(x))=x)$
\item $\exists g \forall x (f(g(x))=x)$
\end{enumerate}

\solution{ %
  a,c,d,e,g 
  %
  }

\eparts


We have proved that the infinite set of real numbers is ``strictly
bigger'' than the infinite set of integers, and the set of integers is
``strictly bigger'' than any finite set.

\bparts

\ppart 

[5 points] State precisely what it means to say a set $A$ is ``strictly
bigger'' than another set $B$.

\solution{ %
There is no injection from $A$ to $B$.  Alternatively, there is no
bijection between $A$ and $B$, while there is an injection from $B$ to
$A$.
}

%\vspace{1.5in}

\ppart 

[5 points] Give an example of a set that is strictly bigger than the set of
real numbers.

\solution{ % 
  $P(\reals)$.
  }

%\vspace{1.5in}

\eparts

%\newpage

\problem [13 points] \textbf{Modular Arithmetic.}

\bparts

\ppart

[5 points] Prove that there is no $x$ such that
\[
117\cdot x \equiv 1 \pmod{213}.
\]

\solution{
$117\cdot x \equiv 1 \pmod{213}$ iff $117 \cdot x + 213 \cdot y = 1$ for
some integer $y$.  This is equivalent to having $\gcd(213,117) = 1$, but
by Euclid's algorithm, $\gcd(213,117) = 3$.
}

%\vspace{3in}


\ppart

[8 points] Find an integer $x$ for which
\[
123 \cdot x \equiv 1 \pmod{2347 } \brule{1in}
\]

\solution{
$x = -706$ works because $1=37\cdot 2347 + (-706)\cdot 123$.
}

%\vspace{2in}

\eparts

%\newpage

\problem [10 points] \textbf{Invariants.}

\bparts

\ppart
Give the definition of a {\it state invariant } of a state machine.

\solution{
A predicate, $P$, on states such that if there is a transition from state
$s$ to state $t$ and $P(s)$ is true, then $P(t)$ is true.
}

%\vspace{2in}

\ppart Besides the identically \texttt{false} and the identically
\texttt{true} state invariants, how many other logically distinct state
invariants does the following machine have?  Describe them. (Two
invariants are \emph{logically distinct} if there exists a state in which
one holds and the other doesn't.)

{\bf State Machine Description:}\\
States $Q \eqdef \set{A,B,C,D,E,F,G,H}$, transitions:
\[
\set{(A,B), (B,C), (C, A), (D,E), (E,F) (F,D), (C,D), (G,A), (B,H)}.
\]

\solution{
Three: the membership predicates for the following three sets of states:
\[
\set{ABCDEFH}, \set{DEF}, \set{H}.
\]
}

\eparts

%\vspace{3in}

%\newpage

\problem [10 points] \textbf{Stars and Bars.}

A juggler plans to juggle 11 rings for his finale.  In his bag are 20
identical red rings, 30 identical blue rings, and 40 identical white
rings.  He must select at least one of each color to be patriotic.  An
example of a patriotic choice of 11 rings would be: 3 red, 2 white, and 6
blue.  How many different patriotic choices are there for the 11 rings?
%\emptybox{1in}{0.6in}

\solution{
This is the same as asking how many ways there are to arrange 11 stars and
two bars such that there is at least one star in each of the three groups
delimited by the bars.  Reserving three stars for this purpose leaves 8
stars and 2 bars, so there are
\[
\binom{8+2}{2} = \binom{10}{2}.
\]
Note that the initial number of red, white, and blue rings available to
the juggler is irrelevant as long as there are at least nine of each.
}

%\vspace{1in}

%\newpage

\problem [10 points] \textbf{Equivalence Relations and Random Variables.}

Define a binary relation $\relz$ on real-valued random variables
$X,Y$ by the rule that $X \relz Y$ iff $\prob{X \neq Y} = 0$.  Prove that
$\relz$ is an equivalence relation.

\solution{
$\relz$ is \emph{reflexive} because the event $X \neq X$ is the empty
event---which has probability zero.

$\relz$ is \emph{symmetric} because the event $X \neq Y$ is the same as the
event $Y \neq X$, so if either of these events has probability zero, then
they both do.

To prove $\relz$ is \emph{transitive}, suppose $X \relz Y$ and $Y \relz Z$.  We
must show that if $X(s) \neq Z(s)$ for some sample point $s$, then
$\prob{s} = 0$.  This implies $\prob{X \neq Z} = 0$, so $X \relz Z$ as
required.

So suppose $X(s) \neq Z(s)$.  If also $X(s) \neq Y(s)$, then $\prob{s} =
0$ because $X \relz Y$.  Otherwise, $Y(s)= X(s) \neq Z(s)$, so $Y(s) \neq
Z(s)$, and hence $\prob{s} = 0$ in this case as well because $Y \relz Z$.
}

%\vspace{3in}

%\newpage

\problem [13 points] \textbf{Counting with Repetition.}

\bparts

\ppart 

[5 points] How many distinguishable ways are there to rearrange the letters in
\begin{center}
``{\bf INSTRUCTOR}''?
\end{center}
%\emptybox{1in}{0.6in}

\solution{There are $10!$ ways to arrange 10 distinct letters, but we have two
T's and two R's, so this overcounts by a factor of $2!$ for the T's
and by a factor of $2!$ for the R's.  The correct answer is
$$\frac{10!}{2! 2!} = 907200$$ 
}

%\vspace{2in}

\ppart 

[8 points] \dots with all vowels consecutive?
%\emptybox{1in}{0.6in}

\solution{
Let the letter V represent the block of vowels, treated as a single
unit.  How many ways can we rearrange the letters NSTRCTRV?  There are
$8!$ ways to arrange 8 distinct letters, but we have two T's and two
R's, so this overcounts by a factor of $2! 2!$.  So there are
$\frac{8!}{2!2!}$ ways to arrange the letters NSTRCTRV.  There are
three vowels, so there are $3!$ ways to arrange the vowels within the
block V, so the number of ways to arrange the letters of INSTRUCTOR
with all the vowels consecutive is
\[
3! \frac{8!}{2!2!} = 60480.
\]

Alternatively: $7!/2!2!$ ways to arrange the consonants, and $8$ places
to insert the $3$ consecutive vowels between these $7$ consonants.
}

%\vspace{1in}
\eparts

%\newpage

\problem [10 points] \textbf{Conditional Probability.}

Boston is justly famous for its enthusiastic sports fans.  Surveys show
that 90\% of adult Bostonians are Celtics fans, and 75\% are Red Sox fans.
However, only 80\% of the Celtics fans are also Red Sox fans.  Now suppose
that an adult Bostonian is chosen at random from among those that are
\emph{not} Celtics fans.  What is the probability that such a person is a
Red Sox fan?  %\emptybox{0.7in}{0.5in}

\solution{
Let $P$ represent the event that a Bostonian is a Red Sox fan, and $S$
represent the event that the resident is a Celtics fan.  Then 
\begin{eqnarray*}
\prob{P} & = & \prob{P  \mid  S} \prob{S} + \prob{P  \mid  \overline{S}}
                    \prob{\overline{S}}, \qquad \text{so}\\
\prob{P  \mid  \overline{S}} & = &
       \frac{\prob{P} - \prob{P  \mid  S} \prob{S}}{\prob{\overline{S}}} \\
& = & \frac{0.75 - (0.80 \cdot 0.90)}{1 - 0.9} \\
& = & 0.3.
\end{eqnarray*}
}

%\vspace{2in}

%\newpage

\problem [10 points] \textbf{Markov Bound.}

A herd of 350 cows is stricken by an outbreak of "mad cow" disease.  The
disease lowers the normal body temperature of a cow, and a cow will die if
its temperature goes below 90 degrees F.  The disease epidemic is so
intense that it lowered the average temperature of the herd to $45$
degrees.  Body temperatures as low as $20$ degrees, but no lower, were
actually found in the herd.

\bparts

\ppart 

[6 points] State a best possible upper bound on the number of cows whose
temperature is high enough to survive.    %\emptybox{0.7in}{0.5in}

\solution{
Let $R$ be the temperature.  Apply Markov's Bound to $R-20$:
\[
\prob{R \geq 90} = \prob{R-20 \geq 70} \leq \expect{R-20}/70 = (45-20)/70 = 5/14,
\]
so at most $(5/14)350 = \textbf{125}$ cows have temperature $\geq 90$
degrees.
}

%\vspace{3in}

\ppart 

[4 points] Give an example set of temperatures that achieve your bound.

\solution{
Of the 350 cows, 125 have 90 degree temperature and 225 have 20
degree temperature.  The mean is
\[
(125 \cdot 90 + 225 \cdot 20)/350 = 45,
\] as required.
}

%\vspace{2in}

\eparts

%\newpage


\problem [15 points] \textbf{Linear Recurrence.}
You just moved into your new house and you are throwing a housewarming
party.  You invite 5 people on the first day and tell them to invite their
friends.  Each newly invited person invites 2 people the day after they
are invited.

\bparts

\ppart

[5 points] Give a recurrence describing the total number of people invited
up to and including the $n$th day, that is, the people you invited, and
the people invited by the people you invited, etc.  For example, on the
first day, 5 people are invited, by the second day 15 people have been
invited---the 5 people invited on the first day and the ten people they
invite on the second day---and by the third day, $35= 15 + 2\cdot 10$
people have been invited.

\solution{
The number, $T(n)$, of people invited through the $n$th day equals the
number, $T(n-1)$, of people invited through the previous day, plus to 2
new guests for each of the $T(n-1) - T(n-2)$ people newly invited on the
previous day, So,
\[
T(n) = T(n-1) + 2 [ T(n-1) - T(n-2) ] = 3 T(n-1) - 2 T(n-2).
\]
}

%\vspace{2in}

\ppart 

[5 points] Describe initial conditions for the recurrence.

\solution{ %
  You know that T(0) = 0 since no one was invited on day 0 and T(1) =
  5, since you invited 5 people on the first day.
  %
  }

%\vspace{2in}

\ppart 

[5 points] Give a closed form expression equal to the number of people invited
by the $n$th day.

\solution{
The characteristic polynomial is $p(a) \eqdef a^2 -3a +2 = (a-2) (a-1)$,
so
\[
T(n) = c2^n + b1^n = c2^n + b.
\]
for some $b,c \in \reals$.
Plugging in the initial conditions, gives two equations:
\begin{eqnarray*}
T(0) & =& 0=c+b\\
T(1)=5 &= &c*2 + b,
\end{eqnarray*}
so $c = 5, b = -5$ and
\[
T(n) = (5 * 2^n) - 5.
\]
}

%\vspace{1.5in}

\eparts

%\newpage

\problem [11 points] {\bf Binomial Identity.}  Suppose you want to choose a team of
$m$ people from a pool of $n$ people for your startup company, and from
these $m$ people you want to choose $k$ to be the team managers.  Prove
that you can do this in
\[
\binom{n}{k}\binom{n-k}{m-k}
\]
ways.

\solution{
First, brute-force:

Choosing $m$ out of $n$, and then $k$ out of the chosen $m$, can be done
in $\binom{n}{m}\binom{m}{k}$ ways.  Now,
\begin{eqnarray*}
\binom{n}{m}\binom{m}{k}
& = & \frac{n!}{m! (n-m)!} \frac{m!}{k! (m-k)!} \\
& = & \frac{n!}{(n-m)! k! (m-k)!} \\
& = & \frac{n! (n-k)!}{(n-m)! k! (m-k)! (n-k)!} \\
& = & \frac{n!}{k! (n-k)!} \frac{(n-k)!}{(n-m)!(m-k)!} \\
& = & \frac{n!}{k! (n-k)!} \frac{(n-k)!}{((n-k) - (m-k))! (m-k)!} \\
& = & \binom{n}{k}\binom{n-k}{m - k}.
\end{eqnarray*} 

Combinatorial proof:

Instead of choosing first $m$ from $n$ and then $k$ from $m$, you could
alternately choose the $k$ managers from the $n$ people and then choose
$m-k$ people to fill out the team from the remaining $n-k$ people.  This
gives you $\binom{n}{k} \binom{n-k}{m-k}$ ways of picking your team.
Since you must have the same number of options regardless of the order in which
you choose to pick team members and managers,
\[
\binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}.
\]
}

%\vspace{5in}

%\newpage

\problem [15 points] \textbf{Trees and Structural Induction.}

A \emph{full binary tree} with its {\it vertices} and {\it leaves} is
defined inductively as follows:

\begin{itemize}

\item A simple graph with one vertex is a full binary tree.  The vertex is
called the \emph{root} of the tree.  The \emph{set of leaves} of the tree
is the set whose sole member is the root.  The \emph{ set of vertices} of
this tree is the same as the set of leaves.

\item If $B_1$ and $B_2$ are full binary trees such that the vertices of
$B_1$ and $B_2$ are disjoint, then a simple graph consisting of a new
vertex with edges from the new vertex to the roots of $B_1$ and $B_2$ is
also a full binary tree, $B$.  The \emph{root of $B$} is the new vertex.
The \emph{vertices of $B$} are exactly its root, the vertices of $B_1$,
and the vertices of $B_2$.  The \emph{leaves of $B$} are exactly the
leaves of $B_1$ and the leaves of $B_2$.

\end{itemize}

For example, a full binary tree with 5 nodes and 3 leafs is is shown in
Figure \textbf{INSERT FIGURE}.

Prove that for all full binary trees $B$,
\[
\card{\text{leaves}(B)} = \frac{\card{\text{vertices}(B)}+1}{2}.
\]

\solution{ %
The induction hypothesis, $P(B)$, is the equation to be proved. 

\textbf{Base case} $P(\text{single root})$: there is 1 leaf, 1 vertex and
indeed $1=(1+1)/2$.

\textbf{Inductive step} $B$ has a root $r$ connected to two full binary
trees $B_1$, $B_2$; the induction hypothesis is that $P(B_1)$ and $P(B_2)$
are true. So
\begin{eqnarray*}
\card{\text{leaves}(B)} & = & \card{\text{leaves}(B_1) \union \text{leaves}(B_2)}\\
 & = & \card{\text{leaves}(B_1)} + \card{\text{leaves}(B_2)} \qquad \text{because
       vertices of $B_1$ and $B_2$ are disjoint}\\
 & = & \frac{\card{\text{vertices}(B_1)}+1}{2} +
       \frac{\card{\text{vertices}(B_2)}+1}{2} \qquad\text{by induction hypothesis}\\
 &= & \frac{(1+ \card{\text{vertices}(B_1)}+
                \card{\text{vertices}(B_2)}) + 1}{2}\\
 & = & \frac{\card{ \set{r} \union \text{vertices}(B_1) \union
             \text{vertices}(B_2)} + 1}{2} \qquad \text{disjointness again}\\
 & = & \frac{\card{\text{vertices}(B)} + 1}{2}
\end{eqnarray*}
}

%\vspace{5in}

%\newpage

\problem [20 points] \textbf{Chebyshev Bound.}

A man has a pocketful of $n$ keys, exactly one of which will open the door
to his apartment.  He picks a random key from his pocket, tries to open
the door with it, and puts it back in his pocket if it doesn't work (no,
he isn't very together about key management, and he may try the same key
over and over again).  He continues trying until he finds the key that
works.

\bparts

\ppart

[5 points] What is the expected number of trials of keys the man makes
until he finds the right one?  \hint Mean time to failure.
%\emptybox{0.7in}{0.5in}
 
\solution{
The probability of picking the right key on each trial is $1/n$, so mean
time to failure---in this case ``failing'' to pick the wrong key---is
$1/(1/n) = n$.
}

%\vspace{2in}

\ppart  

[10 points] What is the variance for the number of trials, $T$, of keys
till he finds the right one ?  \hint Some relevant summation formulas are
in the Appendix.
%\emptybox{1in}{0.7in}

\solution{
The probability stays the same on all subsequent trials since the picked
key is always returned to the urn.  Thus
\[
\prob{T=k} = \left(\frac{n-1}{n}\right)^{k-1}\frac{1}{n}{.}
\]
Note: this is the same as the waiting time for the first head in the
Bernouli process with a biased coin.  Let $p=1/n$ and let $q=1-p$.

The variance of $T$ can be computed directly from the formula,
\[
\variance{T} = \expect{T^2} - \expectsq{T}.
\]
Again, by definition we have
\[
\expect{T^2} = \sum_{k=1}^\infty{k^2 pq^{k-1}}{.}
\]
We know that
\[
\sum_{k=1}^\infty{kq^k} = q\sum_{k=1}^\infty{kq^{k-1}} = \frac{q}{(1-q)^2}.
\]
Moreover,
\begin{eqnarray*}
\sum_{k=1}^\infty{k^2 q^{k-1}} &=& \sum_{k=1}^\infty{\frac{d\, k q^k}{dq}}\\
 &=& \frac{d(\sum_{k=1}^\infty{k q^k})}{dq}\\
 &=& \frac{d (\frac{q}{(1-q)^2})}{dq}\\
 &=& \frac{1}{(1-q)^2} + \frac{2q}{(1-q)^3} = \frac{1}{p^2} + 
\frac{2q}{p^3}{.}
\end{eqnarray*}
Finally, the expectation $\expect{T^2}$ is
\[
\expect{T^2} = p \left(\frac{1}{p^2} +\frac{2q}{p^3}\right) = 
\frac{1}{p} + \frac{2q}{p^2},
\]
and the variance is
\[
\variance{T}= \frac{1}{p} + \frac{2q}{p^2} - (\frac{1}{p})^2 = \frac{q}{p^2} = n(n-1).
\]
}

%\vspace{3in}

\ppart 

[5 points] What is the Chebyshev upper bound on the probability that the
man will make at least a 100 trials till success?  Let $V$ denote the
variance that you were asked to calculate in the previous part, and
express your answer as a closed formula using $V$.
%\emptybox{1in}{0.7in}

\solution{

One-way bound:
\[
\prob{T \geq 100} = \prob{T-n \geq 100-n} \leq \frac{V}{V+ (100-n)^2}.
\]

Full credit also for using the regular two-way bound.
}

%\vspace{1in}

\eparts

%\newpage

\problem [30 points] \textbf{Random Graphs.}

A simple graph with 10 vertices is constructed by randomly placing an edge
between every two vertices with probability $p$.  These random edge
placements are performed independently.

\bparts

\ppart 

[2 points] What is the probability that a given vertex, $v$, of the graph has
degree two?  %\emptybox{1in}{0.6in}

\solution{
$\binom{9}{2} \cdot p^2\cdot ({1-p})^7$.
}

%\vspace{1in}

\ppart 

[5 points] What is the expected number of nodes with degree two? %\emptybox{2in}{1in}

\solution{
10 times the previous answer by linearity of expectations.
}

%\vspace{2in}

\iffalse
\ppart Are $X_i$ and $X_j$ independent for $i\neq j$?  Prove
your answer.

\solution{
No.

Prob($X_i=9$ and $X_j=0$)=0 $\neq Prob(X_i=9)\cdot Prob(X_j=0)$
}
\fi

\ppart 

[15 points] What is the expected number of cliques of size $k$, that is,
subgraphs isomorphic to the complete graph with $k$ vertices?  Express
your answer as a closed form formula involving binomial
coefficients. %\emptybox{1.5in}{0.7in}

\solution{
The strategy for computing the expected number of cliques uses linearity
of expectation.  Define an indicator random variable for every possible
$k$-clique.  Every $k$-subset of the $n$ nodes is a possible $k$-clique,
so there are $\binom{n}{k}$ such random variables.  (Here $n=10$, but the
argument is easier to follow with $n$ as a parameter.)  The random
variable for a particular $k$-clique is 1 if the $k$-clique appears in the
graph and 0 if not, so its expected value is just the probability that a
particular $k$-clique occurs in the graph.  This happens if and only if
all $k$ nodes are connected by edges; there are $\binom{k}{2}$ such edges,
so the probability of a particular $k$-clique is $p^{\binom{k}{2}}$.
Summing the expected values of all the $k$-cliques gives the expected
number of $k$-cliques:
\[
\binom{n}{k} p^{\binom{k}{2}}.
\]
}

%\vspace{1in}

\ppart 

[8 points] The previous result implies an interesting fact which you may
assume without proof: if $p=1/2$, then the expected number of cliques of
size $2 \log n$ is greater than one, where $n$ is the total number of
vertices in the graph.  (In the previous parts we had $n=10$; now $n$ is
arbitrary.)  Oddly, even though we can expect there to be such a clique,
no procedure is known to \emph{find} some clique of size $2\log n$ in the
graph---when there is one---which is much more efficient than exhaustively
searching through all possible subsets of vertices of size $2 \log n$ and
checking each subset to see if it is a clique.  Circle each of the
following expressions which correctly bounds the number of subsets such an
exhaustive search would examine:
\begin{enumerate}
\item $O(2^n)$
\item $O(n^2)$
\item $O(n^{\log n})$
\item $O(n^{2 \log n})$
%\item $\Theta(e^{\log^2 n})$
%\item $\Theta((\log n)^n)$
\end{enumerate}


\solution{
(a),(d).

The number of such subsets is
\[
\binom{n}{2 \log n} = \frac{P(n, 2 \log n)}{(2 \log n)!} < P(n,2 \log n) <
n^{2 \log n},
\]
and 
\[
\frac{P(n, 2 \log n)}{(2 \log n)!} > \left(\frac{(n- \log n)}{2 \log n}\right)^{2 \log
n} > (n^{0.9})^{2 \log n} = n^{1.8 \log n} \neq O(n^{\log n}).
\]
}

\eparts

%\newpage

\problem [15 points] \textbf{Probabilistic Prediction.}

We have three coins to flip: one has probability 3/4 of coming up
heads, another has probability 7/8 of coming up heads, and finally there
is one with probability 15/16 of coming up heads.  One of the three coins
is picked, and this coin is repeatedly tossed.

Explain a way to determine a number of tosses sufficient to allow
identification with 99\% confidence of the coin being tossed.  You do not
have to carry out the calculation, and you may cite without proof any of
the results from the Appendix or other course material.


\solution{
Identify the coin to be the one whose probability is closest to the
fraction of heads among $n$ flips.  This identification will be correct
99\% of the time if the probability that the actual fraction of heads in
$n$ flips differs from the expected fraction of heads by more than 1/32 is
at most 0.01.  We choose 1/32 because it is half the distance between the
two closest coin probabilities.

Let $S_n$ be the number of heads appearing in $n$ flips, so $S_n/n$ is the
fraction of heads.  We assume the successive flips are independent, so the
variance of $S_n/n$ is $1/n^2$ times the variance of $S_n$ which is $n$
times the variance of a Bernoulli variable whose probability was the
probability of heads in one flip.  We know the variance of a Bernoulli
variable is at most 1/4, so $\variance{S_n/n} \leq (1/n^2)(1/4)n = 1/4n$.
Chebyshev's bound implies that the probability that $S_n/n$ deviates from
its mean by 1/32 is at most $(1/4n)/(1/32)^2$.  Choose $n$ so this
quantity is at most 0.01.

Alternatively, observe that $S_n$ will have a Bernoulli distribution with
one of the three probabilities 3/4, 7/8, 15/16.  Using the bounds from
Lecture 21 on the tails of the binomial distribution, we could choose $n$
large enough that the probability that $\prob{\abs{S_n - pn} \geq n/32}
\leq 0.01$ for each $p = 3/4, 7/8,$ and 15/16.
}

%\vspace{4in}

\end{problems}

\iffalse
%\newpage

\section*{Appendix}

\subsection*{Graphs}

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.

A \emph{connected component} of a simple graph is an equivalence class of
vertices under the ``is connected by a path to'' relation on pairs of vertices.

\subsection*{Partial Orders}

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

\subsection*{Sums}

\[
\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).
\]

\subsection*{Combinatorics}

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

\textbf{The Principle of Inclusion-Exclusion}:
\[
\card{A \union B} = \card{A}+ \card{B} - \card{A \intersect B}.
\]
For $n$ sets:
\[
\card{\Union_{i=1}^n A_i}
= \sum_{S \subset \set{1,\dots,n}}
           (-1)^{\card{S}} \card{\Intersect_{j \in S} A_j}.
\]

Probabilistic version:
\[
\prob{A \union B} = \prob{A} + \prob{B} - \prob{A \intersect B}.
\]

\[
\prob{\Union_{i=1}^n A_i}
= \sum_{S \subset \set{1,\dots,n}}
           (-1)^{\card{S}} \prob{\Intersect_{j \in S} A_j}.
\]

\begin{eqnarray*}
n!  & \eqdef & n \cdot (n-1) \cdots 2 \cdot 1\\
0!  & \eqdef & 1\\
P(n,r)  & \eqdef & n \cdot (n-1) \cdots (n - (r-2) \cdot (n - (r - 1))\\
C(n,r) = \binom{n}{r}  & \eqdef & \frac{n!}{r!\, (n-r)!}
\end{eqnarray*}


\subsection*{Markov \& Chebyshev Bounds}

Markov bound for nonnegative random variable, $R$:
\[
\prob{R \geq x} \leq \frac{\expect{R}}{x}.
\]

Chebyshev bound: for an arbitrary random variable, $R$, with standard
deviation $\sigma_R$, and for $c \geq 0$,
\[
\prob{\abs{R - \expect{R}} \geq c\sigma_R} \leq \frac{1}{c^2}.
\]

The ``one-way'' version of Chebyshev bound: for $c \geq 0$,
\[
\prob{R - \expect{R} \geq c\sigma_R} \leq \frac{1}{1+c^2}.
\]


\subsection*{Weak Law of Large Numbers for Bernoulli Variables}

A \emph{Bernoulli variable} is a 0-1-valued random variable.  For any
event $A$, the \emph{index variable}, $I_A$, is the Bernoulli variable
which is 1 exactly when event $A$ occurs.

Let $G_1, G_2, \dots, G_n$ independent Bernoulli variables, each with the
same probability $p$ of being equal to one.  In this case, $G_i=G_i^2$, so
\[
\expect{G_i^2} = \expect{G_i} = \prob{G_i=1} = p,
\]
and
\[
\variance{G_i} = \expect{G_i^2} - \expectsq{G_i} = p - p^2 = p(1-p).
\]
Let
\[
S_n \eqdef \sum_{i=1}^n G_i,
\]

We can use the random variable $S_n/n$ to estimate $p$.  This estimator
$S_n/n$ is a random variable with two critical properties:
\begin{eqnarray*}
\expect{\frac{S_n}{n}} & = & \expect{G_i} = p,\\
\variance{\frac{S_n}{n}} & = & \frac{\variance{G_i}}{n} = \frac{p(1-p)}{n}.
\end{eqnarray*}

To prove this, note that by linearity of expectation
\[
\expect{\frac{S_n}{n}} = \frac{\expect{\sum_{i=1}^n G_i}}{n}
   = \frac{\sum_{i=1}^n \expect{G_i}}{n}
   = \frac{np}{n} = p.
\]

Also, since the $G_i$'s are independent, their variances will add, so
\begin{eqnarray*}
\variance{\frac{S_n}{n}} & = & (\frac{1}{n})^2 \variance{S_n}\\
& = & (\frac{1}{n})^2 \sum_{i=1}^n \variance{G_i}\\
& = & (\frac{1}{n})^2 n\variance{G_i}\\
& = & \frac{\variance{G}}{n}.
\end{eqnarray*}

Now Chebyshev's Bound tells us that
\begin{theorem*}
Let $S_n \eqdef \sum_{i=1}^n G_i$ where $G_1, \dots, G_n$ are mutually
independent Bernoulli variables with the same probability $p$ of being
equal to one.
Then
\[
\prob{\abs{\frac{S_n}{n} - p} \geq x} \leq \frac{p(1-p)}{nx^2}.
\]
\end{theorem*}

Now if we fix $p$ and $x$ and let $n$ approach infinity, we conclude that
the Weak Law of Large Numbers holds:

\[
\lim_{n \rightarrow \infty} \prob{\abs{\frac{S_n}{n} - p} \geq x} = 0.
\]
\fi

\end{document}
