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

\begin{document}

\examinitials{Final}{May 23, 1997}

\begin{closeitemize}
\item This quiz is closed book.  Three crib sheets are allowed.

\item Put your name on the top of {\bf every} page---{\bf these pages
will be separated for grading.}

\item Write your solutions in the space provided.  If you need more
space, write on the back of the sheet containing the problem.  Please
keep your entire answer to a problem on that problem's page.

\item Do not spend too much time on any problem.  Read them all
through first and attack them in the order that allows you to make the
most progress. 

\item Show your work, as partial credit will be given.  You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it.  {\bf Be neat}.

\item This quiz ends at 12 noon.  It contains 11 problems. You will
  get 10 extra points for writing your name, tutorial TA and time
  clearly.

\item GOOD LUCK!
\end{closeitemize}

\smallskip

\renewcommand{\arraystretch}{.22}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& &\hspace*{1in}\\
Problem&Points&Grade\\
& &\\
\hline
\hline
& &\\
name & 10 & \\& &\\ \hline & &\\
1 &  15 & \\& &\\\hline & &\\
2 &  15 & \\& &\\\hline& &\\
3 &  10 & \\& &\\\hline& &\\
4 &  10 & \\& &\\\hline& &\\
5 &  10 & \\& &\\\hline& &\\
6 &  15 & \\& &\\\hline& &\\
7 &  15 & \\& &\\\hline& &\\
8 &  15 & \\& &\\\hline& &\\
9 &  20 & \\& &\\\hline& &\\
10&  15 & \\& &\\\hline& &\\
11&  20 & \\& &\\\hline& &\\
12&  15 & \\& &\\\hline& &\\
13&  15 & \\& &\\
\hline
\hline
& &\\
Total & 200 & \\
& &\\
\hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}
\bigskip\bigskip

\noindent Name:\ \mbox{}\hrulefill\mbox{}\par
\bigskip \bigskip
\noindent Please circle your tutorial TA:
 \hspace{.7in} Terry
 \hspace{.7in} David
 \hspace{.7in} Dimitri
\bigskip

\noindent Please circle your tutorial  time: 
\hspace{.5in} 1
\hspace{.5in} 2
\hspace{.5in} 3
\hspace{.5in} 7
\newpage

\begin{problems}


%TRUE/FALSE
% (lec 8/9) (15m)
\problem\points{15} Circle True/False.

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

\item $p \wedge (\neg p \rightarrow (p \vee \neg q))$ is a tautology
\item $((\forall x) [P(x) \implies (\forall y) Q(y)]) \wedge (\exists
  z) \neg Q(z)$ implies $(\forall w) \neg P(w)$.
\item There is an integer solution to the equation $17x+144y=3$
\item The function $f:\rationals^+ \rightarrow \reals^+$ defined by
$ f(x) = \sqrt{x}$ is a surjection
\item The function $f:\rationals^+ \rightarrow \reals^+$ defined by
$ f(x) = \sqrt{x}$ is an injection
\item The relation $\{(A,B) \mid \mbox{ there is a surjection from $A$
    to $B$}\}$ is transitive.
\item The relation $\{ (f,g) \mid f=\Theta(g) \}$ on functions is an
  equivalence relation.
\item If $R$ and $S$ are transitive relations on $A$, then $R \circ
S$ is transitive.
\item If $R$ and $S$ are reflexive relations on $A$, then $R \cap S$
  is reflexive.
\item The set of prefixes of the decimal representation of $\pi$ is
  uncountable.
\item The set of real numbers between $0$ and $1$ that have only $2$s 
and $9$s in their decimal representation is countable.
\item $|2^{\reals}| < |\reals^5|$
\item There is no set whose power set has the same cardinality as the
  natural numbers.
\item A 14-vertex graph with simple cycles of 10 different lengths is
  not bipartite.
\item $n!=o(n^{\log n})$
\end{list}
 
%7m
\problem \points{15} Short answers.  No need to be rigorous, though
partial credit may be given based on the derivation.
\begin{problemparts}
\ppart What equivalence relation on a nonempty set $A$ is also a poset on $A$?
\ppart How many simple cycles of length 7 are there in an $n$ vertex
complete graph?
\ppart What is the coefficient of $x^{30}$ in $(5+x)^{50}$?
\ppart The space shuttle runs 3 identical computers so that if one
goofs, the other two will outvote it with the right answer.  If each
computer goofs independently with probability $10^{-7}$, what is the
probability that the right answer will prevail?
\ppart Suppose I flip 6 coins and then roll a 6-sided die for each
head I see.  What is the expected number of spots I will see?
\ppart 
Find asymptotic ($\Theta$) bounds for the summation
$$
\sum_{k=1}^{n}\frac{\ln k}{k}
$$

\end{problemparts}

%2m
\problem\points{10}  Give a counterexample to the following claim and then
explain {\bf succinctly}
why the proof is wrong.

Claim: if every horse in a herd is the same color as some other horse
in the herd, then all horses in the herd are the same color.

Proof: Induction on the number of horses.  Base case of 2 horses
trivial: under the hypothesis, one must be the same color as the
other.  So consider a set of $n$ horses satisfying the criteria, and
suppose we add an $(n+1)^{st}$ horse.  By assumption, this horse is
the same color as some other horse.  By inductive hypothesis, that
horse is the same color as all the other horses.  So all the horses
including the $(n+1)^{st}$ are the same color.

\problem \points{10} %(lec 7) (1m)
Prove that
$(A - B) \bigcap (A \bigcup \overline{B} ) = A \bigcap \overline{B}$

\problem \points{10} %(lec 8)
Suppose that there are 6 possible mistakes that could be made in
answering the previous question.  Given that the class has 120
students, show that two of them will make exactly the same set of
mistakes. 

\problem \points{15} % (lec 10) (5m)
 Consider the following algorithm on a poset $\preceq$ over
$x_0,\ldots,x_n$.

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

$x \leftarrow x_0$\\
for $k=1$ to $n$\\
\> if $x_k \preceq x$ then\\
\> \> $x \leftarrow x_k$\\
return $x$
\end{tabbing}

Prove that the above algorithm returns a minimal element of the poset.

 
\problem \points{15} % (lec 14) (10m) 
Solve the following recurrences:
\begin{problemparts}
\ppart %5m
The recurrence 
\[T(n)=2T(n/2)+6n\]
subject to the initial condition $T(1)=1$.
\ppart The recurrence
\begin{displaymath}
f(n) = 4f(n-1)-4f(n-2)
\end{displaymath}

subject to the initial conditions $f(0) =0, f(1) = 3$.

\ppart As I go down a flight of stairs, each time I take a step I can
choose to descend 1 stair or 2 stairs.  Derive (and justify) a
recurrence (and base cases) for the number of different ways I can go
down $n$ stairs (two ways are different if they encounter different
sets of steps).  Determine the number of ways I can go down a flight
of 8 steps.

\eparts

\problem \points{15} %(lec 16) (5m) 
Consider the following identity:
\[
\sum_{k=0}^n {n \choose k} 2^k = 3^n
\]
\bparts
\ppart Prove this identity using the binomial theorem.
\ppart Prove this identity via a combinatorial argument. (Hint:
consider the number of ways to donate some subset of
your $n$ baseball cards to two museums.  For one side, consider where
each card ends up.  For the other, consider where the cards you donate
end up)
\eparts



\problem \points{20} % (lec 17) (12m) 
My favorite bagel store offers 14 different kinds of bagels
and 30 different spreads.  Justify your answers to the following questions:

\bparts

\ppart How many different items does the store sell?

\ppart 150 bagels in the store have poppy seeds on them, 200 have
sesame seeds, and 100 have rye seeds.  Among those bagels, 100 have
sesame and poppy, 80 have sesame and rye, and 40 have poppy and rye.
Among those, 20 have all three kinds of seeds.  How many bagels have
at least one kind of seed?

\ppart How many different sandwiches are available (1 bagel variety, 1
spread)?

\ppart How many distinguishable bags of 12 bagels (no spreads) can I buy?

\ppart If I choose one of those distinguishable bags uniformly at random, what
is the probability that I get 12 different bagel varieties?

\ppart If I choose a spread for each of my 12 bagels uniformly at
random, what is the probability that all of my bagels get different spreads?

\ppart Suppose I throw each of my 12 bagels randomly into one of 3
bags.  What is the probability that I get 4 bagels in each bag?

\eparts



\problem \points{15} %(8m)
$20\%$ of the theorems in the lecture notes contain typos. For any
   theorem, it is the case that if you ask a TA whether it has a typo
   the probability that their answer is correct is $0.9$.  TAs answer
   independently of one another.
\bparts
\ppart 
Given a theorem selected uniformly at random, if a TA tells you that it has a typo, what is the
     probability that it does?   
\ppart 
If $2$ TAs tell you a theorem has
     a typo, what is the probability that it does?
\ppart If one TA tells you a theorem has a typo, what is the
   probability a different TA will tell you the theorem has a typo?
\eparts

\problem \points{20} When we grade this exam, our plan is the
following.  Independently for each of the 14 whole questions (ignoring
parts, but {\bf including your ``name''}), we will randomly assign
full credit (with probability 3/5) or no credit (with probability
2/5).

\bparts

\ppart What is your expected score on problem 1?

\ppart What is your expected score on the exam?

\ppart Based on the expectation, how can you bound the probability
that your score exceeds 160?

\ppart What is the variance of your score on problem 1?

\ppart What is the variance of your exam score?

\ppart Based on the variance, how can you bound the probability your
score is less than 100?

\ppart Give a strong upper bound on the probability that you get a 0
(that is, that no credit is assigned to any one of the 13 problems).

\ppart Suppose that instead of making an independent random choice for
each question, we assigned full credit on all of them with probability
3/5 and 0 credit on all of them otherwise.  Which of the previous
problem parts have unchanged answers, and why?

\ppart Suppose instead that the exam consisted of 1000 true/false
questions, and that we randomly chose to give you credit for each
independently with probability 3/4.  Give a strong upper bound on the
probability that you get more than 800 credits.

\eparts


\problem \points{15} %(lec 23)
I have an urn containing balls of $c$ distinct colors, where
there are $k_i$ balls of color $i$ and $\sum k_i=n$.  I
perform the following experiment:
\begin{enumerate}
\item pick a ball, note its color, and put it back
\item repeatedly choose a ball from the urn and replace it, until I
  get a ball the same color as the first.
\end{enumerate}

\begin{problemparts}

\ppart Conditioning on the fact that the first ball has color $i$,
what is the expected number of picks I make in the second step?

\ppart If I do not condition on the color of the first ball, what is
the expected number of picks I make in the second step? 

\end{problemparts}


\problem \points{15} %(lec 11)
Let $G=(N,E)$ be a simple graph, i.e., an undirected graph
with no self-loops.  A subset of nodes $S\subseteq N$ is an {\em
  independent set} if no two nodes in the set are adjacent (connected
by an edge).  Prove {\bf by induction on the number of vertices} that any
graph with maximum degree $\Delta$ has an independent set of size at
least $n/(\Delta+1)$.

\end{problems}
\end{document}


\problem

After final exam scores are assigned, I will choose a letter grade of
A, B, or C uniformly at random for each student.  Suppose that 40 of
the students deserve A's, 40 deserve B's, and 40 deserve C's.  Call a
student ``happy'' if they get a grade no lower than they deserve.

\bparts

\ppart What is the expected number of happy students?

\ppart give the best bound you can on the probability that there are
more than 90 happy students.

\ppart Call a student ``confused'' if they get a different grade from
what they deserve.  Give the best bound you can on the probability
that the number of confused students exceeds 90.

\eparts

\problem

Prove 
$(\neg p \vee q) \wedge ( \neg p \rightarrow \neg r) \wedge (q \rightarrow r)
\rightarrow ( p \wedge q \wedge r) \vee ( \neg p \wedge \neg q \wedge \neg r)$


%Recurrences and Wald's theorem
%The Boston Vampire strikes back!
\problem
A vampire arrives in Boston at day $0$ and starts biting people at day $1$.
Vampires bite $4$ persons a day, but not all of them become vampires.
The procedure works as follows: 
If a person is bitten by a vampire he becomes a vampling with probability $.5$ 
(otherwise the person is not converted). 
A vampling starts biting $4$ persons on the next 
day after he/she was bitten and makes them vamplings with probability $0.2$.
On every day after the vampling becomes a full grown vampire and bites
people with probability $0.5$.

Define the random variables

$X_t =$ total number of vamplings and vampires on day $t$.

$Y_t^i =$ total number of people bitten by vampire $i$ that become vampires on day $t$.

\bparts
\ppart Derive an expression for $X_{t+1}$ as a function of $X_t$ and $Y_t$.
\ppart Take expectations in the expression of part (a) and derive a recurrence for
the total expected number of vampires and vamplings.
(You do not need to solve the recurrence).
\eparts

\problem  Let $T$ be a non-trivial tree on $n$ nodes.  Let $S$ be a subgraph of
$T$
that is also a tree and contains all the leaves of $T$.  Use well-ordering
on $n$ to prove that $S = T$.



\problem Cardinality

 Prove that the set of all finite graphs is countable.
\problem  Prove that the following algorithm returns
$\overline{\bar{A} \cup ( \bar{B} \cap C)}$.

\begin{tabbing}
Three-to-one($A, B, C$)\\
1 \ \ \ \= $S \leftarrow \phi$\\
2 \> $D \leftarrow A$\\
3 \> while $D \neq \phi$\\
4 \> \ \ \ \= choose an element $x$ of $D$\\
5 \>       \> if ($x \in B$) or ($x \not \in C$)\\
6 \>       \> \ \ \ \= $S \leftarrow S \cup \{x\}$\\
7 \> return $S$
\end{tabbing}

%hard
\problem 
Show by induction

\begin{displaymath}
\sum_{k=1}^{m+1} {m+1 \choose k} \frac{(-1)^{k+1}}{k+1} = \frac{m+1}{m+2}
\end{displaymath}

{\it Hint: manipulate the expression
$ (1+x)^{m+1} = \sum_{k=0}^{m+1} {m+1 \choose k} x^k $ }

\problem
An urn contains $90$ \$1 bills, $9$ \$5 bills, and $1$ \$50 bill. Let
the random variable $X$ be the denomination of the bill selected at
random from the urn.
\bparts
\ppart
Describe the underlying space $S$ of this random experiment and specify the probabilities of its elementary events.

\ppart 
Describe the sample space of $X$, $S_X$, and find the probabilities
for the various values of $X$.

\ppart
Find the expected value of $X$. In what sense is the mean the
break-even price of a ticket for the right to draw a single bill from
the urn?

\eparts

\problem
Obtain an exact solution to the recurrence relation which is defined for all powers of $3$.

\begin{displaymath}
x(n) = 4x(\frac{n}{3})-4x(\frac{n}{9})+ln(n) \\
\end{displaymath}

subject to the initial conditions $x(1) = 0 , x(3) = ln3$. \\
You are also given that a particular solution to this equation (a solution that satisfies the equation but not the initial conditions) is \\
$x_p(n) = ln(n) + 4ln3$

%graphs, inclusion-exclusion and probability
%NOTE: contains my terminology.  Maybe it needs to be fixed
\problem 
A vertex in a tournament graph is called a dominator if all the edges connected to it
are outgoing.  

\bparts
\ppart Show that any tournament graph can have at most one dominator.
\ppart Consider a random tournament on $n$ vertices (ie, each edge is equally likely
to have one of the two directions).
 Find the probability that a particular vertex
of this tournament is a dominator.
\ppart Find the probability that the random tournament has a
dominator.  Explain why your answer is correct.
\eparts



\problem (lec 8) Functions

\bparts
\ppart Consider the function $f:\reals \rightarrow \reals^+$ defined by
$$
f(x) = 
\begin{cases} 
  |x|^3 & \text{if } x \geq 0\\
  x^2 &  \text{if } x < 0\\
\end{cases}
$$
\begin{enumerate}
\item Is $f$ a surjection?
\item Is it an injection?
\item Is it a bijection?
\end{enumerate}

\ppart Consider the function $f:\rationals^+ \rightarrow \reals^+$ defined by
$ f(x) = \sqrt{x}$.
\begin{enumerate}
\item Is $f$ a surjection?
\item Is it an injection?
\item Is it a bijection?
\end{enumerate}

\eparts



\problem (lec 15) In class we claimed that the $k^{th}$ power of the
adjacency matrix of a graph counts the number of (possibly nonsimple)
paths of length exactly $k$ between pairs of vertices. But our
argument was sloppy since we hadn't yet discussed rules for counting.
Use the basic counting rules (for sums, products, inclusion-exclusion,
etc.) to prove the inductive steps of the claim.  That is, prove that
if $A$ is the adjacaency matrix of $G$, and $A^{k-1}$ contains, in its
$u,v$ entry, the number of distinct length $k-1$ paths from $u$ to
$v$, then $A\cdot A^{k-1}$ contains, in its $u,v$ entry, the number of
distinct length $k$ paths from $u$ to $v$.

\problem (lec 20)

Fred is a dog food salesman and as a buying incentive he is giving out
samples of dog food.  He makes calls door to door but leaves a sample
onle on those calls for which the door is answered and a dog is in
residence. On any call the probability of the door being answered is
$3\over4$ , and a probability that any household has a dog is
$2\over3$.  Assume the events ``Door answered'' and ``A dog lives
here'' are independent and also the outcomes of all calls are
independent.  
\bparts
\ppart
Sketch the event space for each call.  Define a call to be successful
if the door is answered and a dog is in residence.  What is the
probility of success and failure? 

\ppart
Determine the probabbility that Fred gives away his first sample on
his third call.

\ppart
Given that he has given away exactly four samples on his first eight
calls, determine the conditional probability that Fred will give away
his fifth sample on his eleventh call.

\ppart
Determine the probability that he gives away his second sample on his
fifth call.

\ppart
Given that he did not give away his second sample on his second call,
determine the conditional probability that he will leave his second
sample on his fifth call.

\ppart
Let's say that Fred ``needs a new supply'' immediatly after the call
on which he gives away his last can of dog food.  If he starts out
with two cans, determine the probability that he completes at least
five calls before he needs a new supply.

\ppart
If he starts out with exactly $m$ cans, determine the expected value
and variance of $d_m$, the number of homes with dogs which he passes
up because of no answer before he needs a new supply.
\eparts


\problem (lec 17/22)
A dart is thrown nine times at a target consisting of three areas.
Each throw has a probability of .2, .3, and .5 of landing in areas 1,
2, and 3, respectively.  Find the probability that the dart lands
exactly three times in each of the areas.

\problem (lec 25)  %chebyshev
The mean response time and the standard deviation in a multi-user
computer system are known 15 seconds and 3 seconds, respectively.
Estimate the response time is more than 5 seconds from the mean.

\problem (lec 25)
One tenth of $1\%$ of a certain type of RAM chip are defective.  A
student needs $50$ chips for a certain board.  How many should she buy
in order for there to be a $99\%$ chance or greater of having at
least 50 working chips?           


\problem (lec 13)
As I descend the ten stairs from my appartment, I can, with each
step, descend exactly one stair or exactly two stairs.  
\bparts
\ppart How many different ways can I descend these stairs? (Hint: find
a recurrence for the number of waus to descend $n$ stairs, and crank
through to 10.) 
\ppart How many ways can I descend if I skip exactly 3 stairs? 
(Hint: consider inserting the ``skips'' among the ``steps.'')
\eparts



\problem (lec 22)
We are given two Bernoulli processes with the probability of success
$P_1$ and $P_2$.  A new process is defined to have a success on its
$k^{th}$ trial ($k = 1, 2, \ldots $) only if {\it exactly} one one of the
other two processes has a success on its $k^{th}$ trial.  

\bparts
\ppart
Determine the probability distribution for the number of trials up to and including the
$r^{th}$ success in the new process.
\ppart
Is the new process a Bernoulli process?
\eparts


\problem (lec 22/23)
Computer $A$ sends a message to computer $B$ over an unreliable
telephone line.  The message is encoded so that $B$ can detect when
errors have been introduced into the message during a transmission.
If B detects an error, it requests A to retransmit it.  The
probability of transmission error is $q=.1$.
\bparts
\ppart
What is the expected number of {\it retransmission} requests and the variance?

\ppart
What is the probability that a message needs to be transmitted more
than two times?

\eparts

\problem (lec 24)
A random variable $x$ is equally likely to have any of the values
$\{1, 2, 3, 4\}$.  A fair coin is tossed independently until the first
head is obtained.  For each tail observed before the first head an
independent experimental value of $x$ is obtained.  Random variable
$r$ is defined to be the sum of all experimental values of $x$
obtained according to this procedure.  Evaluate the expectation and
standard deviation of $r$.


% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
% LocalWords:  TAs vampling vamplings
