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

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

%\newcommand{\pr}{\problem}

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

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

\newcommand{\newgcd}[2]{{\ms{gcd}}(#1, #2)}

\newcommand{\pr}{\newpage\problem}
\newcommand{\cdpg}{\cleardoublepage}
%\newcommand{\cdpg}{}
\newcommand{\npg}{\newpage}
%\newcommand{\npg}{}
%\renewcommand{\bparts}{\begin{testproblemparts}}
%\renewcommand{\eparts}{\end{testproblemparts}}

\begin{document}

\examinitials{FINAL EXAM}{December 17, 1996}


\begin{closeitemize}
\item This exam is closed book. You may use three handwritten crib sheets. 
{\bf No calculators allowed. You may leave your answers in terms of
the ratio of products of numbers and binomial coefficients}.

\item Put your name on the top of each page.

\item Write your solutions in the space provided.  If you need more
space, write on the back of the sheet containing the problem.

\item Show your work, as partial credit will be given. Full credit will not 
be given for unjustified answers.  {\bf Be neat}.

\end{closeitemize}

\bigskip

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

\noindent
{Name:\underline{\hspace*{5in}}}

\bigskip

\noindent Please circle your tutorial TA's name: 
\hspace{.8in} Dimitri
\hspace{.8in} Gunnar

\bigskip

\noindent Please circle your tutorial time:
\hspace{.3in} 10
\hspace{.3in} 11
\hspace{.3in} 12
\hspace{.3in} 1
\hspace{.3in} 2
\hspace{.3in} 3
\newpage

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cdpg
\pr 
\points{10}

Recall the definition of Fibonacci numbers:
\begin{eqnarray*}
F_0 & = & 0 \\
F_1 & = & 1 \\
F_{n} & = & F_{n-1} + F_{n-2} \quad \mbox{for $n \geq 2$}
\end{eqnarray*}
\bparts
\ppart
Prove by induction that ~~~$3 | (F_{n+8} - F_n)$,~~for $n \geq 0$.
\vspace{3in}
\ppart
%Prove that every third Fibonacci number is even.
Prove that ~~~$3 | F_n$~~~if and only if~~~$4 | n$,~~for $n \geq 0$.
({\em Hint}: Use the result from part (a).)
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cdpg
\pr 
\points{10}

\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.
\vspace{3in}
\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.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cdpg
\pr
\points{10}

%(state machines)

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)$}
}{}

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

\bigskip

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

%Give a strengthened version of Inv1, called Inv2, that implies
%Inv1 and that can be proved by induction.
%Inv2:

%(ANS: 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 decendants of $v$.)

%Why is Inv2 true in the base case?

%ANS:  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?

%ANS:  When $\ms{summarize}(v)$ 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$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cdpg
\pr 
\points{15}

The following three parts are unrelated.
\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.  
%Luckily, vampires live only for four days; at the end
%of their fourth day vampires die by such calamities as exposure to
%light or wooden stakes driven through their hearts.
%For each $n \geq 2$, $n$ vampires die on day $n$ by such 
%calamities as exposure to light or wooden stakes driven through their hearts.
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.}

%Solution
%\begin{displaymath}
%f(n) = f(n-1) + 4f(n-2)+ 2(f(n-1)-f(n-2)) - n= 3f(n-1) + 2f(n-2) - n
%\end{displaymath}

\vspace{1.5in}

\ppart
Obtain Tight ($\Theta$) asymptotic bounds for the recurrence
$$
T(n) = 2T(\lceil n/2 \rceil) + \frac{8}{9}T(\floor{3n/4 + \sqrt{n}}) + 
n^2, ~~~\mbox{for $n\geq 100$}
$$
You may assume that $T(n) = \Theta(1)$ for $n=O(1)$.
%Solution
%$\Theta(x^2 \log\log(x))$

\vspace{2in}

\ppart
Find tight ($\Theta$) asymptotic bounds for the summation
$$
\sum_{i=n}^{\infty}{\frac{1}{i^2}}
$$

%Solution
%$$
%\int_2^{n+1}{\frac{ln(x)}{x}dx} \leq \sum_{i=1}^{n}{\frac{ln(i)}{i}}
%\leq \int_2^{n}{\frac{ln(x)}{x}dx} +\frac{ln(2)}{2} \Rightarrow
%\sum_{i=1}^{n}{\frac{ln(i)}{i}} = \Theta(ln(n)^2)
%$$

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cdpg
\pr
\points{15}

In a (five-card stud) poker game, two players $A$ and $B$ are dealt
$5$ cards each at random from the {\em same} standard deck of $52$.
%You may leave your answers in terms of the ratio of a product of
%integers and binomial coefficients.

\bparts
\ppart
A {\em straight flush} consists of $5$ consecutive cards from the same
suit.  (Ace, 2, 3, 4, 5 is the lowest and 10, Jack, Queen, King, Ace
is the highest, so an Ace may not be in the middle of a straight
flush.)  What is the probability that player $A$ gets a straight
flush?

\vspace{2in}

\ppart
A {\em four-of-a-kind} consists of $4$ cards of the same rank (for
example, four $7$s or four Kings).  The fifth card can be anything.
What is the probability that player $B$ gets a four-of-a-kind?

\vspace{2in}

\ppart
What is the conditional probability that player $B$ gets a four-of-a-kind
{\em given} that player $A$ gets a straight flush?

\newpage

\ppart 
What is the probability that player $A$ gets a straight flush {\em
and} player $B$ gets a four-of-a-kind?

\vspace{3in}

\ppart
What is the probability that player $A$ gets a straight flush {\em
given} player $B$ gets a four-of-a-kind?

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cdpg
\pr
\points{10}

\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.
\vspace{2in}
\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 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.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cdpg
\pr
\points{10}

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?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cdpg
\pr
\points{18}

%(Expectation)

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.
\vspace{2in}
\ppart
 You roll one ordinary die.  You win a number of dollars that is
equal to six times the number of spots. 
\vspace{2in}
\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.
\newpage
\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.
\vspace{2in}
\ppart
 You roll two six-sided dice.  You win the product of the number of
spots that appear on the two dice.
\vspace{2in}
\ppart
 You roll one ordinary die.  You win a number of dollars that is
the square of the number of spots.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cdpg
\pr
\points{10}

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,
what fraction of humans can have EQ$\geq 1500$?

\vspace{3in}
\ppart
Assuming that the standard deviation of 
EQ is~100, what fraction of humans can have EQ$\geq 1500$?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cdpg
\pr
\points{12}

A pentium chip has 753 components.
Past experience with Intel engineers indicates that 
225 of these components fail with probability $1/15$,
400 fail with probability $1/10$, 
and 128 fail with probability $1/8$.
Assume that all component failures are independent.
\bparts
\setlength{\itemsep}{3.5in}	
\ppart
What is the expected number of components that will fail on a pentium chip?
\ppart
Compute the variance for the number of components that will fail on a
pentium chip.
\newpage
\ppart
Derive a formula for the exact probability that a pentium chip has 
no failures.
\ppart
Derive an upper bound of the form $e^{-x}$, where $x$ is an integer,
on the probability that a pentium chip has no failures.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cdpg
\pr
\points{15}

In an effort to relieve congestion on the Internet, ARPA is
considering building SUPERNET.  SUPERNET is a heierarchical routing
network for which the country is divided into 6 regions: New England
(NE), New York (NY), Washington DC (DC), the south (SO), Los Angeles
(LA), and the rest of the country (RE).  The 6 regions will be
connected with 9 ultra-high bandwidth, bidirectional links so that
region $u$ is directly connected to region $v$ if and only if 
$u\in\{\mbox{NE,NY,DC}\}\mbox{, and}~ v\in\{\mbox{SO,LA,RE}\}$.
\bparts
\ppart
Draw the graph corresponding to the ultra-high bandwidth connections.\\
Is the graph planar? Is it bipartite?
\vspace{5in}
\ppart
When a message on the SUPERNET needs to go from one region to another,
it travels on a shortest path through the ultra-high bandwidth
network.  In the event that there is more than one shortest path, then
a shortest path is picked uniformly at random from among the shortest
paths.  (Note that there is always a unique shortest path or exactly
three shortest paths.)  ARPA engineers believe that there will be 15
million messages per second emanating from each region and that each
such message has a random destination (i.e., each message is destined
for each of the 5 other regions with equal probability--the message
cannot stay within the region).  What is the expected message load on
each ultra-high bandwidth connection? When counting load,
make sure to count messages that are travelling in either direction.
({\em Hint}: The expected load on each edge is the same.) 
\vspace{3in}
\ppart
Because of budget cutbacks, ARPA engineers have been forced to do
without buffers and so if ever the message traffic across a link
during a second of time exceeds its capacity, the entire SUPERNET will
come to a crashing halt.  The president has decreed that the
probability of such a crash during the next 4 years should be at most
$10^{-9}$.  ARPA has the option of buying links with capacity
$\sqrt{E},
E/2, .99E, E, 1.01E, 2E, 2.718E$, and $E^2$ (where $E$ is the expected load
that you computed in part (b) above), but the cost of a link goes up with
its capacity.  Your job is to decide the least expensive link that
will fit within the President's mandate.  You may assume that the
destinations of each of the messages are mutually independent.
There are at most $e^{19}$ seconds in 4 years.\\

Which capacity should you choose?  Show your work and justify your
answer.  Compute an upper bound of the form $e^x$, where $x$ is an
integer on the probability that SUPERNET crashes in the next 4 years
given your choice of link capacity.  (You may use the following
facts: $e^{-21}<10^{-9}<e^{-20},~
\ln(1.01)+1/1.01 = 1.00005,~ \ln 2 +1/2 = 1.19$. These estimates are
close enough for government work.)

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}
\end{document}
