\documentclass[12pt]{article}
\usepackage{amsmath}

\input{macros-course}

\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}


\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\newcommand{\ignore}[1]{}
%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\smallskip \textbf{Solution:} #1}

\newcommand{\script}[1]{\mathbold{#1}}


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

\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{\bij}{\mathop{\mbox{\rm bij}}}

\begin{document}

\handout{conflict}{Conflict Final Solutions}{May 20, 1999}

CORRECTIONS NOT MADE.

\begin{problems}

\problem\pts{35} \textbf{Short Answers.}
\bparts

\ppart An assembly line produces 10001 cars which pass inspection and 19
which do not.  What is the largest $n$ such that there must
have been a run of $n$ consecutive cars which passed inspection?
\brule{1.0in} \solution{501}

\ppart  What is the largest number of edges possible in a two-colorable,
four vertex undirected graph?  \brule{1.0in} \solution{4}

\ppart %F96 Final

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.  How many
suit-distributions are there?

\solution{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 $\binom{13 + 4 - 1}{4 - 1} = 560.$
}


\ppart In an employment interview, a Southern California weather forecaster
honestly promises at least 95\% accuracy for his daily predictions of
sunshine versus rain.  Is this an impressive credential for the job?
Briefly explain.

\solution{Unimpressive: he could be 95\% accurate by always predicting
sunshine.  It would be impressive if his daily prediction was 95\% accurate
\emph{given that it rained}.}



\ppart In a path in an undirected tree with $n$ vertices, what is the
largest number of edges possible? \brule{0.7in}

\solution{$n-1$}

\ppart What is the coefficient of $x^{12}$ in the polynomial $(7x+3)^{50}$?
(Your answer may contain binomial coefficients and integer powers.)

\solution{LATER}



\ppart Write a closed form expression for $\Pi_{k=1}^\infty 2^{2^{-k}}$. \brule{1in}

\solution{$2^{\sum_{k=1}^\infty 2^{-k}} = 2^1 = 2$}

\eparts


\iffalse
\problem\pts{???} \textbf{Cardinality.}  Let $P(A)$ denote the powerset of a
set $A$.  Prove there is no bijection between $S$ and $P(P(S))$ for any set
$S$.

\solution{By contradiction.  If there was such a bijection, then there is
an surjection from $S$ to $P(P(S))$.  But there is an obvious surjection
$P(P(S))$ to $P(S)$, namely map every one-element set $\set{T}\in P(P(S))$
to $T \in P(S)$ (and map all the other elements of $P(P(S))$ to an
arbitrary member of $P(S)$---say the empty set).  Since the composition of
surjections is a surjection, we conclude there is an surjection from $S$ to
$P(S)$, contradicting Cantor's Theorem.}
\newpage
\fi

\newpage

\problem\pts{25} \textbf{Cardinality.}  Let $A$ be an infinite set and $B$
be a finite set.  Show that there is a bijection $g:A \union B \to A$.

\solution{If $A \union B = A$ there is trivially a bijection, so we may
assume there is at least one element in $B-A$.  Let $b_0,b_1,\dots,b_{n-1}$ be
the elements in $B-A$ where $n> 0$.  Since $A$ is infinite, there is an
injection $f:\naturals \to A$.  Define $g:A \union B \to A$ as
\[g(x) = \left\{\begin{array}{ll}
            f(i) & \mbox{if }x = b_i\\
            f(j+n) & \mbox{if }x = f(j)\\
            x & \mbox{otherwise.}  
\end{array} \right.
\]
}

\iffalse

\problem\pts{15} \textbf{Counting.} A standard deck of $52$ cards plus two
additional jokers is shuffled so that each of the permutations of the 54
cards are equally likely.  What is the {\bf probability} that no two spades
are adjacent in the shuffled deck?  (All you need to know about jokers is
that they are not spades.)  You may express your answer using factorials
and binomial coefficients.

\solution{13 spades are ``bars.''  The other cards are ``stars.''  Place
one star in each of the 12 places between bars.  This leaves $54 - 13 -12 =
29$ stars to place among the bars; there are $\binom{29 + 13}{13}$ such
patterns of stars and bars.  There are $13! \cdot (54 -13)!$ shuffles
matching each pattern, and the total number of shuffles is $54!$, so the
probability of no two adjacent spades is
\[
\binom{29 + 13}{13} \cdot 13! \cdot (54 -13)!/54! = \binom{29 +
13}{13}/\binom{54}{13} = 29!/54!
\]}



\newpage

\problem\pts{20} \textbf{Conditional Probability}

Several years ago there was a gender discrimination lawsuit against a
certain Institute.  The plaintiff's evidence of discrimination was
admissions data for the past decade showing that in every Institute
department, the percentage of male applicants accepted was \emph{greater}
than the percentage of female applicants accepted.  The Institute's defense
attorneys argued that plaintiff's evidence, while accurate, was misleading.
They pointed out that the same admissions data revealed that the acceptance
rate among all male applicants---irrespective of department--- was actually
\emph{lower} than the acceptance rate among all female applicants!

For simplicity suppose that the only departments at the Institute were EE
and CS, and consider the experiment where we pick a random applicant.
Define the following events:
\begin{tabular}{rcl}
A & ::= & applicant is accepted,\\
F & ::= & applicant is female,\\
M & ::= &  applicant is male,\\
CS & ::= & applicant applied to CS,\\
CS & ::= & applicant applied to EE.
\end{tabular}
Assume that all applicants are either male or female, and that no
applicant applied to both departments.
\iffalse
That is, the events $F_{EE}$,
$F_{CS}$, $\mbox{M-EE}$, and $\mbox{M-CS}$ are all disjoint.
\fi

\bparts

\ppart  The plaintiff's observation is that in both EE and CS, the
probability that a woman is accepted is less than the probability that a
man is accepted.  This observation can be precisely expressed with a couple
of inequalities between conditional probabilities involving the events
above.  State these inequalities.

\solution{
\begin{eqnarray*}
\Pr(A \mid F \intersect EE) & < & \Pr(A \mid M \intersect EE) \\
\Pr(A \mid F \intersect CS) & < & \Pr(A \mid M \intersect CS).
\end{eqnarray*}
}



\ppart  Express the defense attorneys' retort that overall a woman
applicant is {\em more} likely to be accepted than a man as an inequality
between conditional probabilities involving the events above.

\solution{
\begin{eqnarray*}
\Pr(A \mid F) & > & \Pr(A \mid M)
\end{eqnarray*}
}



\ppart Although the assertions above may appear to be logically
inconsistent, both the plaintiff's and the defense's claims about the
conditional probabilities can be correct. (Never mind whose interpretation
of the data we find more persuasive.)

Fill in the four table entries below to provide hypothetical applicant
statistics for which both the plaintiff and the
University attorneys' assertions are true.

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
     & Applied & Accepted & percent accepted\\
 & & & \\ \hline \hline & & &\\
Dept & Females & Females &  Females\\
& & & \\ \hline
CS & & & \\ & & & \\ \hline & & &\\
EE & & & \\ & & & \\ \hline \hline & & &\\
Dept & Males & Males & Males\\
& & & \\ \hline
CS & & & \\ & & & \\ \hline & & &\\
EE & & & \\ & & & \\ \hline & & &\\
\hline & & &\\
Total & &  & \\
& & &\\
\hline
\end{tabular}
\end{center}

\solution{
\[
\begin{array}{ccr}
\mbox{CS} & \mbox{0 females accepted, 1 applied} & 0\% \\
          & \mbox{50 males accepted, 100 applied} & 50\% \\
\mbox{EE} & \mbox{70 females accepted, 100 applied} & 70\% \\
          & \mbox{1 male accepted, 1 applied} & 100\% \\
\hline
\mbox{Overall} & \mbox{70 females accepted, 101 applied} & \approx 70\% \\
          & \mbox{51 males accepted, 101 applied} & \approx 51\%
\end{array}
\]
}

\eparts
\fi

\newpage
\problem\pts{20} \textbf{Probability of Graph Assertions.}  A digraph with
vertices $\set{1,2,\dots, n}$ is called an \emph{$n$-digraph}.  Given an
$n$-digraph, $G$, let ``$d(x,y)$'' be the assertion that $G$ has a directed
edge from vertex $x$ to vertex $y$.

\bparts

%\ppart How many $n$-digraphs are there? \brule{1in} \solution{$2^{n^2}$}

\ppart\pts{2} How many $n$-digraphs satisfy the assertion $\forall x, y : d(x,y)$?
\brule{1in}\solution{1}

\iffalse
\ppart How many $n$-digraphs satisfy the assertion $\exists x, y : d(x,y)$?
\brule{1in}\solution{$2^{n^2}-1$}
\fi

\medskip

Suppose we randomly select an $n$-digraph, with all $n$-digraphs equally
likely to be selected.

\iffalse
\ppart Prove that there is nonzero probability that the selected
$n$-digraph satisfies both of the following assertions:
\[\begin{array}{l}
\forall x_1 \exists x_2 \exists x_3 \forall x_4 \forall x_5 \exists x_6 :
d(x_1,x_2) \vee d(x_3,x_4) \vee d(x_5,x_6) \vee  d(x_3,x_1)\\
\exists x_1 \forall x_2 \forall x_3 \exists x_4 \exists x_5 \exists x_6 :
d(x_1,x_2) \wedge d(x_3,x_4) \wedge d(x_5,x_6) \wedge  d(x_3,x_1)
\end{array}\]

\solution{We need only show that some $n$-digraph satisfies both assertions.
The complete $n$-digraph is one.}



\ppart Let $p$ be the probability that the selected $n$-digraph satisfies
the first assertion in the previous part.  Explain why the probability that
it satisfies the second assertion $1-p$.

\solution{The second assertion is the complement of the first assertion if
we replace $d(\cdot,\cdot)$ with $\not (\cdot, \cdot)$ throughout.  Now a
graph $(V,E)$ satisfies such a logical assertion iff its complement graph
$(V,V^2 - E)$ satisfies the assertion when we replace $d(\cdot,\cdot)$ with
$\not d(\cdot, \cdot)$ throughout.  This defines a bijection between the
sample points satisfying the formula and its replacement, so the
probabilility of an assertion is the same as the probability of the
assertion with $d$ replaced by $\not d$.  Hence the probability of the
second assertion is the same as the probability, $1-p$, of the complement
of the first one.}
\fi

\ppart\pts{7} Show that the probability that the selected graph satisfies $\forall
x \exists y : d(x,y)$ approaches 1 as $n$ approaches infinity.

\solution{For given $x$, the probability that there is no edge to all of
the vertices (including itself) is $1/2^n$, since the existence of each
edge is independent of the others.  So the probability that there is some
edge out of $x$ is $1- 1/2^n$.  Whether one value of $x$ has this property
is independent of whether any other does, so the probability that all the
vertices have this property is 
\[
(1- 1/2^n)^n = (1 - (n/2^n)(1/n))^n \sim e^{n/2^n}
\]
which approaches 1 as $n$ approaches infinity.}



\ppart\pts{7} What is the expected number of directed simple cycles (that is, cycles
going through each vertex exactly once) in the selected graph?

\solution{
\begin{eqnarray*}
\lefteqn{ \expect{\mbox{number of cycles through a particular
simple cycle of vertices}}}\\
 & = & \prob{\mbox{all edges present in a particular cycle of the
vertices}}\\
& = & 1/2^n.
\end{eqnarray*}
The number of simple cycles is $n!/n$ so the expected number of cycles is
$n!/n2^n$.}


\ppart\pts{4}  Circle all that apply: the expected number of simple cycles is
\[
=\Omega (e - 0.001)^{n \ln n}; \qquad
=O(e + 0.001)^{n \ln n}; \qquad
=\Theta(e^{n \ln n}); \qquad
\sim e^{n\ln n}/(2e)^n
\]

\solution{the first two.}

\iffalse
\ppart Show that the expected number of simple cycles is $\Omega (e -
0.001)^{n \ln n}$.

\solution{Using Stirling's formula
\[n!/n2^n \sim \sqrt{2\pi/n}(n/e)^n/2^n = \sqrt{2\pi/n}e^{n\ln n}/(2e)^n.\]
But $e^{n\ln n} = [(e - 0.001)\alpha]^{n\ln n}$ where $\alpha = e/(e -
0.001) > 1$, so
\begin{eqnarray*}
\sqrt{2\pi/n}e^{n\ln n}/(2e)^n & = &
\sqrt{2\pi/n}\alpha^{n \ln n}(e- 0.001)^{n\ln n}/(2e)^n\\
& = & \sqrt{2\pi/n}(e- 0.001)^{n\ln n}(\alpha^{\ln n}/2e)^n\\
& \geq  & \sqrt{2\pi/n}(e- 0.001)^{n\ln n}3^n\\
& = & [\sqrt{2\pi/n}3^n](e- 0.001)^{n\ln n}
\end{eqnarray*}
when $n$ is large enough that $\alpha^{\ln n} \geq 6e$.  Since the final
bracketed expression grows unboundedly, the whole final expression is
$\Omega((e- 0.001)^{n\ln n}).$ }


\fi

\eparts

\newpage

\iffalse

\problem\pts{20}  \textbf{Probability of Assertion}
Let $A$, $B$, and $C$ be mutually independent random
variables taking on values in the range $1$ to $n$ uniformly.  What is
the probability that the following statement is true?

\[
\neg ((A \geq B) \vee (A \geq C)) \wedge
	\exists x \ ((B < x \wedge x < C) \vee
		     (C < x \wedge x < B))
\]

Assume that the universe is the set of natural numbers.

\solution{
The statement says that $A$ is less than $B$ and $C$ and there is some
number between $B$ and $C$.  The number of assignments to $A$, $B$,
and $C$ satisfying this statement is
\[
2 \cdot \binom{n-1}{3}.
\]
Therefore, the probability that a random assignment is satisfying is
\[
\frac{2 \cdot \binom{n-1}{3}}{n^3}.
\]}

\fi

\newpage

\iffalse
\problem\pts{15} \textbf{Counting.}  How many arrangements of the letters
$\set{a,l,m,e,y,e,r}$ are there that don't contain the consecutive letters
\emph{eye} or \emph{ram}?

\solution{
\begin{eqnarray*}
\mbox{All arrangements} & = & 7!/2!\\
\mbox{Arrangements with eye: use} \set{eye,a,l,m,r} & = & 5!\\
\mbox{Arrangements with ram: use} \set{ram,l,e,y,e} & = & 5!/2!\\
\mbox{Arrangements with ram and eye: use} \set{ram,eye,l} & = & 3!\\
\mbox{Arrangements with neither ram nor eye}
      & = & 7!/2! - 5! - 5!/2! + 3! = 2346,
\end{eqnarray*}
by inclusion/exclusion.
}
\fi

\problem\pts{10} %S98 Final
\textbf{Coefficients.}  Prove that the number of sequences of eleven
letters which can be made from the letters in MISSISSIPPI is not divisible
by four.

\solution{See Spring 98}



\problem\pts{20} \textbf{Bayes' Theorem.} One percent of the population is
infected with a sexually transmitted disease (STD).  There are two
over-the-counter tests which detect STD infection.  Test A gives 95\%
reliable results for both infected and uninfected individuals.  Likewise
for Test B but with 90\% reliability.  The correctness of each test is
independent of the other.
\bparts

\ppart
If the tests are performed on someone infected with STD, what is the
probability that both tests return positive?

\solution{$P(A \intersect B|H) = P(A|H) * P(B|H)
         = 95\% * 90\%
	 = 85.5\%$}



\ppart You apply both tests to yourself and both come back positive.  What
is the probability that you actually have an STD?

\solution{
\begin{eqnarray*}
\lefteqn{P(H|A \intersect B)  =  P(A \intersect B|H) * P(H) / P(A \intersect B)}\\
         & = & P(A \intersect B|H) * P(H) / ( P(A \intersect B|H) * P(H) + P(A \intersect B|-H) * P(-H) )\\
         & = & P(A \intersect B|H) * P(H) / ( P(A \intersect B|H) * P(H) + P(A|-H) * P(B|-H) * P(-H) )\\
	 & = & .855 * 0.01 / ( .855 * 0.01 + .05 * .10 * .99)\\
	 & = & 1.68\% \mbox{BUGGY ARITHMETIC?}
\end{eqnarray*}
}



\eparts

\newpage

\iffalse
\problem\pts{20}        

In this problem we are going to prove a case of {\bf Vandermonde's
theorem} which says:
\[
\sum_{i=0}^n \binom{n}{i}^2  =  \binom{2n}{n}
\]

\bparts
\ppart A {\bf lattice path} is a path from a point in the plane with
integer coordinates to another point where each step in the path is
either one unit to the right or one unit up.  Show how many lattice
paths exist from (0,0) to $(p,q)$ by applying a bijection between
paths and an appropriate set of binary strings.

\solution{Each path corresponds to a string of $(p+q)$ bits where $p$
of them are ones.  We choose $p$ out of the total $p+q$ positions to
be one, yielding $\binom{p+q }{ p}$ possibilities.}



\ppart Prove the theorem above combinatorially by showing that both sides
count the number of lattice paths from $(0,0)$ to $(n,n)$. \hint classify the
paths by the poin on the diagonal from $(n,0)$ to $(0,n)$.

\solution{Each path from (0,0) to $(n,n)$ passes through some point
$(i,n-i)$.  There are $\binom{n }{ i}$ paths from (0,0) to $(i,n-i)$ and
$\binom{n }{ n-i}$ = $\binom {n }{i}$ paths from $(i,n-i)$ to $(n,n)$.  No
paths are double-counted because no path can go through two points on
the diagonal $y=n-x$.  The total number of paths is then $\sum_{i=0}^n
\binom{n }{ i}^2$.}

\eparts
\fi

\newpage
\problem\pts{20} \textbf{Wald's Theorem.}

(THIS PROBLEM IS BUGGY, cf., THE ACTUAL FINAL)

If the decimal digits of $\pi$
behaved like a ``random'' sequence, how soon would 6.042 turn up?  More
precisely, suppose successive digits from zero to nine were generated
independently until the four digit sequence ``6042'' appeared.  What is the
expected number of digits generated?  \hint Parse the sequence into
consecutive ``tries to get 6042'', where a try is either a single digit
other than 6, or a 6 followed by a single digit other than 0, or or a 60
followed by a single digit other than 4, etc.  For example, the sequence
365760160604576042 parses into nine tries:
\[3/65/7/60/1/60/6045/7/6042.\]

\solution{By Wald's Theorem, the expected number is the mean time to a
successful try, namely $10^4$, times the expected
length of a try, which is
\[
1 \cdot \frac{9}{10} + 2 \cdot \frac{1}{10}\frac{9}{10} + 3 \cdot
(\frac{1}{10})^2\frac{9}{10} + 4 \cdot (\frac{1}{10})^3
 =  (900 + 180 + 27 + 4)/1000 = 1111/1000
\]
Thus on average, we will have to read 11110 digits of $\pi$ in order to see
``6042''.}

\newpage

\problem\pts{20}

Solve the following linear recurrence:
\[
F_n  =  \frac{6 F_{n-1} - F_{n-2} + (1/2)^n}{9}
\]
subject to the initial conditions $F_0$ = 2, $F_1$ = 7/6.

\bparts
\ppart Obtain a particular solution.
\solution{$(1/2)^n$}



\ppart Solve the homogeneous equation.

\solution{$c_1 (1/3)^n + c_2 n (1/3)^n$}



\ppart Combine the particular and homogeneous solutions to solve for $F_n$.

\solution{$F_n = (1/2)^n + (1/3)^n + n(1/3)^n$}



\ppart Solve the infinite series $\sum_{n=0}^\infty F_n$ using any method
you wish (but show your work).

\solution{$\frac{1}{1-1/2} + \frac{1}{1-1/3} + \frac{1/3}{(1-1/3)^2} =
17/4$.}



\eparts

\iffalse
1)  	COUNTING  (ps7, 1996)  --> We can change the #s around a bit

	How many ways are there to distribute eight balls into six
	distinct boxes with the first two boxes having collectively at
	most four balls if

	(a) the balls are identical?

	ANSWER:  Placing exactly _r_ balls in the first 2 boxes can be done
		in 

	W(r,n,k) = [(r+2-1) choose (2-1)] * [(n-r + k-2 - 1) choose (k-2 - 1)]

	ways.  First term is way to place r balls in first 2 boxes, 2nd term
	is way to place remaining n-r balls into remaining k-2 boxes.

	So n=8 k=6 r=4 implies the answer is:
(note that these #s can and should be changed)

	SUM (from i=0 to 4) W(i, 8, 6) = (i+1 choose 1) * (11-i choose 3)=1056

	(b) the balls are distinct?

	Same reasoning:

	(n choose r)  -  # ways to select r balls to place in first 2 boxes

	2^r - # ways to place selected balls in the first 2 boxes

	(k-2)^(n-r)  -  # ways to place un-selected balls in last k-2 boxes

	D(r, n, k) = (n choose r) * 2^r * (k-2)^(n-r)

	For our case, n=8 k=6 r=4 answer is:

	SUM (over i=0 to 4) = (8 choose i) * 2^i * 4^(8-i) = 1531904

\problem
(This was an application of pigeonhole used in spring 97 on prob set 8)

Use the pigeonhole principle to prove the following statement:
If G is bipartite, then it contains no odd cycles
\solution{
	Assume there is odd cycle, length 2n+1.  By pigeonhole, at least n+1
	vertices must have the same color.  Two of them must then be adjacent,
	contradiction since graph is bipartite.}

\fi

\iffalse
\problem Let $X_1, X_2, \dots$ be a sequence of independent random
variables such that $\variance{X_i} \leq b$ for some $b \geq 0$ and all $i
\geq 1$.  Let 
\[
S_n ::= X_1 + X_2 + \cdots + X_n.
\]
Prove that for every $\epsilon > 0$
\[
\lim_{n \rightarrow \infty}
        \prob{\abs{\frac{S_n}{n} - \expect{\frac{S_n}{n}}}
 \geq \epsilon} = 0.
\]
\hint We proved this ``weak law of large numbers'' only in the case that
the $X_i$'s came from independent samples of the same 0-1 valued
experiment.
\solution{Same as proof in the notes, simply replacing $\variance{G}$ by
$b$.}
\fi

\problem\pts{20} \textbf{Stable Marriage Problem and Partial Order.}  We
know the ``morning-evening'' protocol yields a man-optimal set of stable
marriages when the men propose, or a woman-optimal set of stable marriage
if we reverse the roles and let the women propose.  In many cases there are
further sets of stable marriages in addition to those produced by our
protocol.  We say that a set, $S_1$, of stable marriages \emph{improves}
another such set $S_2$ if every man likes his wife in $S_1$ at least as
much as his wife in $S_2$.

\bparts
\ppart\pts{8} Prove that \emph{improves} is a partial order on stable marriage sets.


\ppart\pts{2} Characterize the man-optimal and woman-optimal stable marriage sets
in terms of this partial order.

\solution{They are the maximum and minimum elements, respectively.}


\ppart\pts{10} For stable marriage sets $S_1,S_2$ define the set of marriages $S_1
\sqcup S_2$ by letting each man marry whichever of his spouses in $S_1$ or
$S_2$ he prefers.  It turns out, and you may take as given, that $S_1
\sqcup S_2$ defines a marriage set and the set is stable (neither of these
facts is obvious).  Prove that $S_1 \sqcup S_2$ is the least upper bound of
$S_1$ and $S_2$ in the partial order.

\solution{LATER}

 \eparts


\newpage
\problem\pts{20}  %S96 Final

\textbf{Divide and Conquer.}  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)$.

Circle each of the following induction hypothesis that will provide a
correct proof.
\[
\begin{array}{lrcl}
(i) & T(n) & \leq & 4n^2 \\
(ii) & T(n) & \leq & 2n \\
(iii) & T(n) & \leq & 10n \\
(iv) & T(n) & \leq  & 3n+10\\
(v) & T(n)&  \leq & 4n
\end{array}
\]
\solution{(iii) and (v)}


\iffalse
\problem \textbf{Expectation.} %F96 practice final

An integer $X$ is drawn from the set $1,2,\ldots,n$ uniformly at random. 

\bparts

\ppart 
Prove that the probability that $X$ is divisible by $k$ is $(1/n)(\lfloor
n/k\rfloor)$.

\solution{LATER}


\ppart
Prove that the expected number of divisors of $X$ is $\Theta(\ln n)$

\solution{LATER}

\eparts
\fi

\problem\pts{30}

\textbf{Bounds from Mean and Variance.}  $100$ students take an exam. The
total number of points for the exam is $207$.

\bparts

\ppart Given only that the mean on the exam is $60$ and the lowest score
was 20, what is the best upper bound which can be given for the number of
students who scored {\bf more than} $120$? \brule{1in}

\solution{LATER}


\ppart
Given only that the mean on the exam is $60$ and the variance is $72$, what is
the best upper bound you can give on the number of students who scored
{\bf more than} $120$?  \brule{1in}

\solution{LATER}

\eparts
\iffalse

\newpage
\problem %F96 practice final

An exam has $100$ true/false questions and $100$ multiple choice
questions. Each true/false question is worth $1$ point while each multiple
choice question is worth $2$ points. The maximum score is $300$. There is a
student who answers at random. She is correct with probability $1/2$ on
each true/false question and with probability $1/4$ on each multiple choice
question.

\bparts

\ppart What is the expected score of the student? \brule{1in}
\solution{LATER}


\ppart What is the standard deviation of the student's score?  \ppart What
is the best upper bound you can give on the probability that the student
scores more than $272$ points? \brule{1in}


\solution{LATER}

\eparts

\fi

\iffalse
\newpage
\problem\pts{30} %F96 practice final slight revision

An exam has $100$ true/false questions and $100$ multiple choice
questions. Each true/false question is worth $1$ point while each multiple
choice question is worth $2$ points. The maximum score is $300$. There is a
student who answers at random. She is correct with probability $1/2$ on
each true/false question and with probability $1/4$ on each multiple choice
question.
\bparts

\ppart What is the expected score of the student?


\solution{LATER}

\ppart What is the standard deviation of the student's score?


\solution{LATER}

\ppart To give an upper bound on the probability that the student scores
more than $272$ points, one or more among Markov's, Chebyshev's, and
Chernoff's bounds are applicable.  Which ones are applicable?

\solution{All of them.}


\ppart What is the best upper bound on the probability that the student scores
more than $272$ points obtainable using the applicable results from the
previous part?

\solution{Use Chebyshev.}


\eparts
\fi



\end{problems}
\end{document}

