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

\newcommand\answer[1]{{\bf Answer: {#1}}}
\newcommand{\pr}{\problem}
\newcommand{\npg}{\newpage}

\newcommand{\E}{\mbox{\bf Ex}}
\renewcommand{\Pr}{\mbox{\bf Pr}}
\newcommand\vari{\mbox{ \bf Var}}
\newcommand\cov{\mbox{Cov}}
\newcommand\Ex[1]{\mbox{Ex}[\, #1 \, ]}
\newcommand\Prob[1]{\mbox{Prob}[\, #1 \, ]}

\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}

\begin{document}

\handout{oldfinal}{Practice Final}{December 8, 1998}

{\bf This practice final was the actual final exam from Fall 1998.}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
%Induction

\pr 
\points{8}

Recall the definition of the Fibonacci numbers:

$$
F_n = 
\begin{cases}
0 & \text{if $n=0$}\\
1 & \text{if $n=1$}\\
F_{n-1}+F_{n-2} & \text{if $n > 1$}
\end{cases}
$$

\bparts

\ppart{\bf [2 points]}

Which Fibonacci numbers are even? (I.e., find a necessary and sufficient
condition on $n$ that characterizes when $F_n$ is even).
State a theorem of the form: $F_n$ is even if and only if$\dots$

\ppart{\bf [6 points]}

Prove that your answer to part (a) is correct.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
%Tom Leighton
%logic, graphs

\pr
\points{10}

Consider an $n$-player tournament for $n \geq 2$ in which there is a match
between each pair of players.  In each match, there is one winner and one
loser (no ties allowed).  Let $P$ denote the set of players and let 
$W \subseteq P$ denote the subset of players who won the most games 
(I.e., $x \in W$ if $x$ wins $k$ games and no other player wins more 
than $k$ games).
Let $B(x,y)$ be a predicate which is true if and only if
$x$ beats $y$. (Note: $B(x,x)$ is always false).

\bparts

\ppart {\bf [2 points]}

Express the following statement using quantifiers and logical notation.

``For any player $x \in W$ and any other player $z$, either $x$ beats
$z$ or there exists a player $y$ such that $x$ beats $y$ and $y$ beats $z$
(or both)''. 

\ppart {\bf [2 points]}

Write the negation of the preceding statement in logical notation 
without using the negation or complement symbol. Also, do not use the
$\neq$ symbol for this part. (Note: $B(z,x)$ implies $z \neq x$).
You do not need to prove your answer is correct.

\ppart{\bf [6 points]}

Prove the statement in part (a).

({\em Hint: The simplest proofs do \underline{not} use induction.})

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
%Divide and conquer

\pr
\points{8}

Find a closed form expression for $T(n)$ in each of the following sums
and recurrences.  In order to save time in calculations, you can express
your answer using $\Theta$ notation.  You do not need to prove your answer.
(In each case $n \in \nat$, but you can ignore the case 
when $n=0$).

\bparts

\ppart{\bf [2 points]}

\begin{displaymath}
T(n) = \sum_{i=1}^{n} {2 \over i}
\end{displaymath}

\ppart{\bf [2 points]}

\begin{displaymath}
T(n) = \sum_{i=1}^{n} (i+3)
\end{displaymath}

\ppart{\bf [2 points]}

\begin{displaymath}
T(n) = 
\begin{cases}
1  & \text{if $n \leq 4$}\\
T\left(\floor{{n\over 4}}\right)+T\left(\floor{{n\over 3}}\right)+n^2
&  \text{if $n > 4$}\\
\end{cases}
\end{displaymath}

\ppart{\bf [2 points]}

\begin{displaymath}
T(n) = 
\begin{cases}
1 & \text{if $n \leq 4$}\\
2T\left(\floor{{n\over 4}+ \sqrt{n}}\right)+\sqrt{n}
&  \text{if $n > 4$}\\
\end{cases}
\end{displaymath}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
%Linear recurrence

\pr
\points{6}

Solve the following recurrence for $T(n)$.

$$
T(n+1) = 6T(n) - 9T(n-1) + 2^n
$$

with the initial conditions $T(0) = 1, T(1) = -1$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
%counting 
%David

\pr
\points{10}

\bparts

\ppart{\bf [5 points]}

Calculate the number of ways the integers from 1 to 9 can be arranged
so that no even integer is in its natural position. (For example 2 is not
in the second position, and so on).
Specify your answer as an integer or as the sum of products of integers.
(You may include factorials in your answer but not binomial coefficients).

\ppart{\bf [5 points]}

How many strings are there with $n$ 1's, $2n$ 2's, and $3n$ 3's?
Leave your answer in the form of a ratio of factorials.
You do not need to prove that your answer is correct.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
%Graph + prob
%Santosh

\pr
\points{8}

Consider an $n$-node undirected graph $G = (V,E)$.
A simple $k$-cycle $(2 < k \leq n)$ in $G$ is a sequence of distinct
nodes $v_1, v_2, \ldots, v_k$ for which $(v_1,v_2) \in E,
(v_2,v_3) \in E,\ldots,(v_{k-1},v_k) \in E$, and $(v_k,v_1) \in E$.
Note that $v_1, v_2, \ldots, v_k$ is the same cycle as 
$v_2, v_3, \ldots, v_k,v_1$, and so forth.
Also, $v_1,v_2,\ldots,v_k$ is the same cycle as $v_k, \ldots, v_2, v_1$.

\bparts

\ppart{\bf [4 points]}

What is the maximum possible number of distinct simple $k$-cycles in $G$ 
for a given $k$ (assuming all possible edges are present in $G$)?

({\em Note: for $n=3, k = 3$ the answer is 1}).

\ppart{\bf [4 points]}

Now suppose that $G$ is constructed randomly as follows:
For every pair of nodes $\{v_i,v_j\}$, toss a coin of bias $p$
(i.e., the coin is heads with probability $p$).  
Include the edge $\{v_i,v_j\}$ if the coin comes up heads.
Assume that the coin tosses are mutually independent.
What is the expected number of simple $k$-cycles in $G$~?
(If you were not able to solve part (a), you may let
$X$ denote the answer to part (a) and express your answer in terms of 
$X$, $k$, and $p$).

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
%Counting,exp,var
%Dimitri

\pr
\points{9}

The gambling game Yahtzee is played with five fair, mutually independent
 six-sided dice. In the following questions, you may leave factorials
and binomial coefficients in your answer.

\bparts

\ppart{\bf [3 points]}

A {\em Yahtzee} is a throw of the five dice that results in all dice having the
same value.  Find the probability of a Yahtzee.

\ppart{\bf [3 points]}

Find the probability of a straight. A {\em straight} is either a throw of
$\{1,2,3,4,5\}$ or $\{2,3,4,5,6\}$. (Note that the dice are unordered -
e.g., any roll which results in one 1, one 2, one 3, one 4, and one 5
counts as a straight).

\ppart{\bf [3 points]}

A {\em  full house} is a result in which there is a group of three dice with
the same number, and a group of two dice with the same number
(for example $\{2,2,5,5,5\}$ is full-house). A Yahtzee doesn't count as a full
house. Find the probability of a full house.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8
%Russel

\pr
\points{12}

Bobo decides to bet one dollar at a casino.  However, he's not sure
what game he wants to play.

\begin{itemize}
\item The probability that Bobo plays poker is 20\%, 
in which case he has a 30\%
chance of winning {\bf \$2}  and a 70\% chance of losing {\bf \$1}.

\item
The probability that Bobo plays blackjack is 20\%, in which case he has a 40\%
chance of winning {\bf \$1} and a 60\% chance of losing {\bf \$1}.

\item
The probability that Bobo plays the slot machines is 60\%,
in which case he has
a 30\% chance of winning {\bf \$1} and an 70\% chance of losing {\bf \$1}.
\end{itemize}

Let $X$ denote Bobo's winnings when he makes one bet according to the
above probabilities.

\bparts

\ppart{\bf [2 points]}

What is $\E[X]$?

\ppart{\bf [2 points]}

What is $\E[X^2]$?


\ppart{\bf [4 points]}

What is $\vari[X]$?

\ppart{\bf [4 points]}

If we know that Bobo won one dollar at the casino, what
is the probability that he played blackjack?

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9
%Markov,chebychev,Chernov
%Dimitri, Alex

\pr
\points{14}

The spider is expecting guests and wants to catch 500 flies for her
dinner.  The expected number of flies caught in the web per hour is $40$.

\bparts

\ppart{\bf [4 points]}
 
What is an upper bound to the probability that the spider will have caught 500
flies in 10 hours?
 
\ppart{\bf [2 points]}

What is a lower bound to the probability that the spider will have to 
wait more than 10 hours to catch 500 flies?


\ppart{\bf [4 points]}

The spider checks her log and discovers that the standard deviation
for the number of flies caught in an hour is 20.
Find an upper bound on the probability that the spider will catch 500 flies
within 10 hours, using this additional information.

\ppart{\bf [4 points]}

The spider discovers additional interesting information.  
The standard deviation is not 20 after all, but
100 flies pass by her web every hour.  
60 of these flies are quite small and are caught with probability $1/6$ each.
40 of the flies are big and are caught with probability $3/4$ each.
Assume all fly interceptions are mutually independent.
Using this information, find an upper bound on the probability that 
the spider will catch 500 flies within 10 hours.
(Since you don't have a calculator, you may leave $\ln$ and $e$ in 
your answer).

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 10
%Network problem
%Dimitri

\pr
\points{8}

Six computers $c_1,\ldots,c_6$ are connected in a circle so that
$c_1$ is connected to $c_2$ and $c_6$, $c_2$ is connected to $c_1$ and $c_3$
and so forth.
There is also a seventh computer $c_0$ with direct connections to the other six
computers.  When two computers 
want to communicate the signal is transmitted through the shortest path on the
network.  Ties are resolved in favor of the path that does {\bf not}
pass through $c_0$.  
During each second of time, each computer sends one signal.
Each signal is sent to a randomly selected computer (the source and destination
of any signal are always different).
All random selections are drawn from the uniform distribution,
but there may be dependencies.

\bparts

\ppart{\bf [2 points]}
 
Draw the graph of the network.

\ppart{\bf [6 points]}

For each edge, calculate the expected traffic per second
through the edge.
Edges are bidirectional so a signal passing through the edge in either 
direction counts as traffic through the edge.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 12
%random walk
%Tom, Dimitri

\pr
\points{7}

A job queue is operating under the following assumptions:

\begin{enumerate}

\item At the start of each minute (begining at time zero),
a job is removed from the queue for processing (if the queue is nonempty).
This job is processed during the ensuing 60 seconds.

\item During the course of each minute (in between the times when jobs are
removed from the queue), new jobs can arrive in the queue.
The probability that one new job arrives is $1/2$.  The probability that
two new jobs arrive is $1/4$. The probability that no new jobs arrive
is $1/4$.  
The number of job arrivals at each step are mutually independent.

\item The queue overflows if it ever has 10 or more jobs.

\end{enumerate}

Let $R$ be the minute during which the queue first overflows.
(If there are 10 or more jobs in the queue before we start, then
$R = 0$).

Let $J_n = \E[R| \text{$n$ jobs in the spooler before we start}]$.
Set up a recurrence for $J_n$. State special cases and initial conditions.
{\bf Do NOT solve the recurrence}

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

\end{problems}
\end{document}
