\documentstyle[12pt,psfig,epsf]{cmu-art}

\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qedbox}{\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newcommand{\qed}{\nopagebreak\mbox{}\hfill\qedbox\smallskip}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}

%\setlength{\textwidth}{6.50in}
%\addtolength{\oddsidemargin}{-0.75in}
%\addtolength{\evensidemargin}{-0.75in}
%\topmargin -1in
\begin{document}
\centerline{\psfig{figure=tpi.eps,height=1.0in,width=4.0in}}
{\large
\fbox{\parbox{6.1in}{
\hbox to \hsize{\ \ \ QUIZ 3 \hfil Bruce Maggs \hfil April 27, 1998\ \ \ }

\vskip 0.1in
}}}

\noindent
{\bf NAME :} \\ \\
{\bf ANDREW ID :} \\ \\
{\bf SECTION :  \ \ A \ \ B \ \ C \ \ D} \\

\noindent
{\bf INSTRUCTIONS. For the first 7 problems you do not need to give
any reason or justification for your answers. For the remaining
problems you must give complete explanations. WRITE CLEARLY.  WRITE
YOUR NAME AND ANDREW ID ABOVE AND CIRCLE YOUR SECTION.


\newcommand{\problem}[3]{\noindent {\bf #1}. [#2 points] \\ #3 \vspace{24ex}}

\newcommand{\wisdom}[2]{\begin{quotation}
 \begin{center} \bf #1 \end{center} #2 \end{quotation} }

\wisdom{The easy stuff.}{This part is to test your ability to study 
material that has been pre-digested and labeled as useful or
likely to appear on exams. If you do not do well on this section, your
study habits could use adjustment.}

%
% Questions for the ``Repeat After Me'' section
%


\problem{1}{5}{Suppose that $A$ and $B$ are events in a probability space, and
that $\Pr[A] = 0.5$, $\Pr[B] =0.2$, and $\Pr[A \cup B] = 0.6$.  What
is $\Pr[A \cap B]$?}

\problem{2}{5}{Suppose that $X$ is a non-negative integer random variable that
takes on the value $i$ with probability $\Pr[X=i]$.  What is the
definition of $E[X]$, the expectation of $X$?}

\problem{3}{5}{Suppose that each of the 112 students in 15-299 is
assigned uniformly and independently at random to one of four
recitation sections.  What is the probability that all six students named
``Pat'' are assigned to the same recitation section?}

\problem{4}{5}{Draw all of the 5-node undirected graphs (with no
self-loops and no multi-edges) that are not planar.}

\problem{5}{5}{Suppose that an $N$-node planar graph is drawn in the plane
(with no edges crossing) with $F$ faces.  How many edges does the
graph have?}

%\wisdom{Reading Solutions.}{This section tests your understanding of
%the homework assignments, including your ability to read the
%homework solutions that we hand out.}

\newpage

\wisdom{Basic Techniques.}{This part will test your ability to apply
techniques for which I have given explicit recipes. If you do not do
well on this section, your study habits could use adjustment.}

\problem{6}{10}{Suppose that $A$ and $B$ are events in a probability space.
Using the fact that $A = (A \cap B) \cup (A \cap \overline{B})$, prove
that $\Pr[A] = \Pr[A | B] \cdot \Pr[B] + \Pr[A | \overline{B}] \cdot
\Pr[\overline{B}]$.}

\problem{7}{10}{Suppose that a resident of Pittsburgh chosen at random is
a Steelers fan with probability $0.90$, that a resident chosen at
random is a Penguins fan with probability $0.75$, and that a resident
Steelers fan chosen at random is a Penguins fan with probability
$0.80$.  Now suppose that a resident is chosen at random from among
those that are {\it not\/} Steelers fans.  What is the probability
that such a resident is a Penguins fan?}

% answer: 0.3
%
% Pr[P] = Pr[P | S] * Pr[S] + Pr[P | Sbar] * (1 - Pr[S])
%
% Pr[P | Sbar] = (Pr[P] - Pr[P | S] * Pr[S]) / (1 - Pr[S])
%              = (0.75 - 0.80*0.90) / (1 - 0.9)

\problem{8}{10}{Suppose that a fair coin is tossed 100 times.  What is
the expected number of pairs of consecutive flips in which the coin
takes on the same value?}

\newpage

\wisdom{A Moment's Thought!}
{This section tests your ability to think a little bit more
insightfully. You must give complete explanations of your answers.}

The {\it degree\/} of a node in a graph is the number of edges
incident on that node.

\problem{9}{10}{Prove that the average node degree in a finite tree
is less than two.}

\problem{10}{15}{Prove that if the maximum degree in a finite tree is
$d$, then the tree must have at least $d$ nodes of degree one.}

\problem{11}{20}{Suppose that an $n$-node random undirected graph is
formed as follows.  For each pair of distinct vertices $u$ and $v$,
the edge $\{u,v\}$ is present with probability $p$ and not present
with probability $1-p$, independent of whether any other edge is or is
not in the graph.  What should the probability $p$ be set to so that
the expected number of cliques of size $k$ is one?}

\end{document}

