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

\renewenvironment{proof}{\par{\noindent\em Proof.}\hspace{1em}\setlength{\parindent}{0pt}}{\qed}

\newcommand{\Prob}[1]{{\rm Pr}(#1)}
\def\medblank{\rule[-2pt]{1in}{.5pt}}

\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{\ms}[1]{%
        \relax\ifmmode
                \mathord{\mathcode`\-="702D\it #1\mathcode`\-="2200}%
        \else
                $\mathord{\mathcode`\-="702D\it #1\mathcode`\-="2200}$%
        \fi
}
\newcommand{\pr}{\newpage\problem}
\newcommand{\cdpg}{\cleardoublepage}
%\newcommand{\cdpg}{}
\newcommand{\npg}{\newpage}
%\newcommand{\npg}{}
%\renewcommand{\bparts}{\begin{testproblemparts}}
%\renewcommand{\eparts}{\end{testproblemparts}}


\begin{document}
\handout{pfinal}{Practice Final Exam}{May 13, 1997}
\let\comp\circ
\def\blank{\rule[-2pt]{.5in}{.5pt}}
\def\longblank{\rule[-2pt]{2in}{.5pt}}
\begin{problems}

\problem
Let $A$ be a set and $R$ be a binary relation on $A$.  For each of the
statements in the box on the left below, indicate the number of the
formula in the box on the right expressing that property.  (Recall that
the {\em composite} of two binary relations $R$ and $S$, written $S\circ
R$, is the relation $\{(a,c)\mid \mbox{there exists some $b$ such that
$(a,b)\in R$ and $(b,c)\in S$}\}$.  $R^T$ is the {\em transpose} of $R$,
i.e., $R^T=\{(a,b)\mid (b,a)\in R\}$, and $I$ denotes the {\em identity}
relation on $A$, i.e., $I=\{(a,a)\mid a\in A\}$.)

\renewcommand{\arraystretch}{1.2}
\begin{tabular}{|c|l|c|}\hline
a. & $R$ is transitive & \mbox{ \hspace{.2in}   } \\ \hline
b. & $R$ is antisymmetric & \\ \hline
c. & $R$ is reflexive & \\ \hline
d. & $R$ is symmetric & \\ \hline
e. & $R$ is a bijection & \\ \hline
f. & $R$ is an equivalence relation & \\ \hline
g. & $R$ is a partial order & \\ \hline
\end{tabular}
\qquad
$\begin{array}{|cl|}\hline
1. & R = R^T \\ 
2. & R\circ R \subseteq R \\
3. & R\cap R^T \subseteq I \\
4. & R\cap R^T \subseteq I \subseteq R\circ R \subseteq R \\ 
5. & I\subseteq R \\ 
6. & R\circ R^T = R^T\circ R = I \\
7. & I \subseteq R\circ R \subseteq R \subseteq R^T\cap R\\ 
\hline
\end{array}$



\problem Recurrences.

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


\ppart Consider the recurrence $T(n)=T(n/2)+T(n/4)+n$ and $T(1)=1$.
Prove that $T(n) \le 2n$.

\ppart Prove that $T(n)=\Theta(n)$ in the recurrence above.

\eparts

\problem


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

\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



\problem
In this problem, $A$, $B$ and $C$ denote arbitrary sets. $f$ and $g$ are
functions as specified in each part and $I$ denotes the identity function.
For each statement indicate whether it is {\bf T}rue or {\bf F}alse. No
explanation is required.

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

\item
There exists an injection (one-to-one) $f:A\to B$ if and only if there
exists a surjection (onto) $g:B\to A$.

\item
Let $f:A\to B$ and $g:B\to A$. $f\comp g=I$ implies $g\comp
f=I$.

\item
Let $f:A\to B$ and $g:B\to C$. If both $f$ and $g$ are injections,
then $g\comp f$ is an injection.

\item
Let $f:A\to B$ and $g:B\to C$. $g\comp f$ is a surjection implies both
$f$ and $g$ are surjections.

\item
Let $f:A\to B$ be an injection. If $|B|\leq |A|$, then $f$ is a
bijection.

\end{list}

\problem Answer {\bf T} or {\bf F}:
%\mbox{ }

\begin{list}{{\bf T\ \ F\ \ \ }}{\setlength{\leftmargin}{40pt}%
        \setlength{\labelwidth}{\leftmargin}%
}
\item 
The mapping $f_a:Z_p \rightarrow Z_p$ defined by
\[ f_a(x) = ax \pmod{p}\]
is a bijection for any nonzero $a\in Z_p$, when $p$ is prime.
\item
For all $a,b$ in $\naturals$, $\gcd(a^2b,ab^2) = ab$.
\item
If $a^{-1}\pmod{b}$ exists, then
so does $b^{-1} \pmod{a}$.
\item
Let $\lambda(n)$ denote the number of distinct prime factors
of $n$.  Then $\lambda(n) = \Omega(\mbox{lg lg } n)$.
\end{list}

\problem %\mbox{ }
Answer {\bf T} or {\bf F}:

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

\item Adding $k$ edges to an undirected graph increases its chromatic
       number (the number of colors needed to color the vertices)
       by at most $k$.
\item The number of length-$3$ paths in an $n$-vertex undirected graph is
       $O(n^2)$.
\item The number of length-$3$ paths in an $n$ vertex tree is $O(n)$
\item Reversing the directions of all edges in a directed graph leaves
       the number of simple directed cycles unchanged.
\item If an undirected graph has the degree of every vertex divisible
       by a prime $p$, then $p$ must evenly divide the number of edges.
\end{list}



\problem 

Find the number of permutations of the letters 
$\{a,b,c,d,e,f,g\}$ that do not contain 
``bag'' or ``def''.


\problem Consider the following recursive algorithm for coloring a
graph $G$ with natural numbers.  For a vertex $v$, $G-v$ denotes the
graph you get by removing $v$ and all its incident edges from $G$.

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

Color($G$)\\
\> {\bf if} $G$ has 1 vertex $v$\\
\> \> set the color of $v$ to be $0$\\
\> {\bf else}\\
\> \> choose a vertex $v$ of $G$\\
\> \> Color($G-v$)\\
\> \> set the color of $v$ to be the minimum $n \in \naturals$ for
which no neighbor of $G$ has color $n$\\
\end{tabbing}
Prove that this algorithm legally colors $G$ with a number of colors
no more than 1 plus the maximum degree of a vertex in $G$.




\problem


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?



\problem 
A lake contains $n$ trout.  100 of them are caught, tagged and returned to
the lake.  Later another 100 trout are caught, selected independently from
the first 100.

\bparts \ppart Assume that the second 100 trout are selected without
replacement.  Write an expression (in $n$) for the exact probability that
these trout are found to contain exactly 7 tagged ones.




\ppart Now consider selecting the second 100 trout with replacement. That
is, you repeat 100 times the following steps: select at random a trout in
the lake, check if the trout is tagged and return it to the lake before
selecting a new trout.

What is the probability that exactly 7 of the selected trout are
tagged?
\eparts


\problem 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.  \bparts
\ppart How many different suit-distributions are there?



\ppart
How many different suit-distributions are there assuming that you get at
least one card in each suit?



\eparts



\problem
Suppose the entries $a,b,c,d$ of a $2\times 2$ matrix 
\[
        M=\begin{bmatrix}a&b\cr c&d\cr \end{bmatrix}
\]
are chosen independently at random according to the uniform
distribution on $\{0,1,2,3,4\}$.  Let $X = \det(M) = ad-bc$.
\bparts
\ppart What is $E(X)$?



\ppart What is $E(X\mid b = 1)$?


\ppart What is $Var(X)$?


\eparts


\problem


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



\end{problems}

\end{document}
