\documentstyle[12pt,macpsfig,amssymb]{article}
\input{/a/class/6.042/spring95/macros-course}

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

\setcounter{page}{0}

%\newcommand{\pr}{\problem}
%\newcommand{\newnewpage}{}

\newcommand{\pr}{\newpage\problem}
\newcommand{\newnewpage}{\newpage}

\renewcommand{\bparts}{\begin{testproblemparts}}
\renewcommand{\eparts}{\end{testproblemparts}}

\begin{document}

\examinitials{Final Exam}{May 26, 1995}


\begin{closeitemize}

\item This exam is open book; it ends at 4:30 {\sc p.m.}  

\item Put your name on the top of each page.
%	---the pages of this booklet  may be separated for grading.
%	\item Write your solutions in the space provided.  
If you need more space, write on the 
{\em back of the sheet containing the problem}.
%	Please do notpput part of the answer to one problem on the back of 
%	the sheet for another problem.
%
%\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 The grades will be available after Monday 3pm from Professor 
Rivest's secretary, Be. Her phone number is 253-6098 and her email address
is {\tt be@theory.lcs.mit.edu}.

\item Good luck!
\end{closeitemize}

\bigskip
\bigskip

\renewcommand{\arraystretch}{.5}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& &\hspace*{1in}\\
Problem&Points&Grade\\
& &\\
\hline
\hline
& &\\
name & 4 & \\& &\\ \hline & &\\
1 &  12 & \\& &\\\hline & &\\
2 &  12 & \\& &\\\hline& &\\
3 &  12 & \\& &\\\hline& &\\
4 &  12 & \\& &\\\hline& &\\
5 &  12 & \\& &\\\hline& &\\
6 &  12 & \\& &\\\hline& &\\
7 &  12 & \\& &\\\hline& &\\
8 &  12 & \\& &\\
\hline
\hline
& &\\
Total & 100 & \\
& &\\
\hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}
\bigskip
\bigskip
\bigskip

\noindent Name:\ \mbox{}\hrulefill\mbox{}\par
%\bigskip \bigskip
%\noindent Please circle your tutorial TA:
% \hspace{.7in} Jennifer
% \hspace{.7in} Parry
% \hspace{.7in} Steve
% \hspace{.7in} Ravi
%\bigskip
%\bigskip
%
%\noindent Please circle your tutorial  time: 
%\hspace{.5in} 10
%\hspace{.5in} 11
%\hspace{.5in} 12
%\hspace{.5in} 1
%\hspace{.5in} 2
%\hspace{.5in} 3
\newnewpage
\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pr 
\points{12} 

A woman rolls a fair die to obtain a result $X$, and then flips a fair coin 
$X$ times. She reports getting a total of $2$ heads.  

Compute 
% Estimate    why only ``estimate''  the calculations are easy.  -steve
the probability that she observed $X=5$.  Show your work.

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

\pr 
\points{12} 
Let $X$ and $Y$ be independent random variables which take on only positive
values. Prove or disprove:  %  they should know how to ``disprove''  -steve
\[ E\left(\frac{X}{Y}\right)=\frac{E(X)}{E(Y)}     \]
(Assume that $E\left(\frac{X}{Y}\right), E(X)$, 
and $E(Y)$ are all well-defined and 
finite positive quantities. Note: $0$ is not a positive number.)

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

\pr 
\points{12} 

In how many ways can $r$ integers 
be selected from the set $\{1,2, \cdots, n\}$ so that no two are consecutive?

%(Hint: You may first want to find how many ways $r$ men and $s$ women can be
%seated in a row so that no two women sit next to each other.)
%[[[Is this hint really useful?  --Steve]]]

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

\pr 
\points{12} 

The weather in a certain city is somewhat predictable: it is either
sunny or rainy. If it rains one day then it is sunny the
following day with probability $1/3$. If it is sunny one day
then it rains the following day with probability $1/3$. 

Given that it is sunny today, find the average number of sunny
days for the next $n$ days, starting tomorrow.  

%(Hint: Consider the
%probability that after $t$ days it is sunny.)
%[[[What kind of hint is this?  
%Won't they know they have to compute this?  --Steve]]]

\remove{
A certain man has a problem finding work. If he is unemployed
on any given morning, there's constant probability $p_h$(independent
of past history) that he will be hired before that evening; but if
he's got a job when the day begins, there's constant probability $p_f$
that he'll be laid off by nightfall. Find the average number of
evenings on which he will have a job lined up, assuming that he is
initially employed and that this process goes on for $n$ days. (For
example, if $n=1$ then answer is $1-p_f$.)  (Hint: Consider the
probability that the person is employed after $t$ days)
}

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

\pr
\points{12}
A boolean formula is said to be in 3-CNF if it is in conjunctive
normal form and each clause contains exactly $3$ distinct literals.  For
example, 
\[
(x_1 \vee \lnot x_2 \vee x_3) \wedge (\lnot x_1 \vee x_2 \vee x_4)
\]
is in 3-CNF.  Prove that if $\varphi$ is a formula in 3-CNF
then there is an assignment that satisfies at least $7/8$ of its clauses.
(Hint: Use the probabilistic method.)
%[[[Here a hint would be nice:  (Hint: Use the probabilistic method.)  
%--Steve]]]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\points{12}
Let $f$ be a function chosen uniformly at random from the set of all 
functions from $\{1,\ldots,n\}$ to $\{1,\ldots,n\}$.
Let random variable $R$ denote the cardinality of the range of~$f$.

\begin{testproblemparts}
	 \setlength{\itemsep}{3in}	
\ppart What is the expected value of $R$? 
(Hint: Let $X_i$ denote the indicator variable of the event ``$i$ is in 
the range of~$f$'').

\remove{
  \bigskip
  \bigskip
  \bigskip
  \bigskip
  \bigskip
}
\ppart Compute the variance of $R$. The computation should take three steps:
\begin{itemize}
\item Use the principle of inclusion/exclusion to compute $P(X_iX_j = 0)$.
\item Compute ${\rm Cov}(X_i,X_j)$.
\item Compute ${\rm Var}(R)$.
\end{itemize}
You may use the following approximations: 
$ \left(1-{1\over n}\right)^n \approx e^{-1}$
and
$\left(1-{2\over n}\right)^n \approx e^{-2}$.

\newnewpage
\vspace*{0in}
\ppart What can you say about $P(R - E(R) > \lambda \sqrt{n})$?
\end{testproblemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\points{12}
Let $G$ be a tree (a connected acyclic undirected graph) on $n$ vertices.
Let $k\geq 2$ be a fixed integer.  
Determine the number of ways to color the vertices of $G$ with $k$ colors
such that no two adjacent vertices have the same color.  
Prove by induction that your answer is correct. 

(This proof is not difficult.  Most of the points for this problem will
be ``style points'', awarded for clarity, conciseness, and rigor.)

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

Rank the following functions by their orders of growth.
That is, order the functions $f_a, f_b, f_c, f_d$ so that
\[
f_a = O(f_b) \;\;\mbox{ and } \;\;
f_b = O(f_c) \;\;\mbox{ and } \;\;
f_c = O(f_d).
\]
Justify your answers and say whether the $O$'s are asymptotically tight 
or if they can be replaced by $o$'s.

\begin{itemize}
\item $f_1(n)=$ the number of undirected (loop-free) graphs on 
$\{1,\ldots,n\}$.
\item $f_2(n) =$ the number of binary relations on $\{1,\ldots,n\}$.
\item $f_3(n) =$ the number of equivalence relations on $\{1,\ldots,n\}$.
\item $f_4(n) =$ the number of $n \times n$ $(0,1)$-matrices where one-quarter 
of the entries are 1's.
\end{itemize}

\end{problems}

\end{document}

