\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{psfig}
\usepackage{graphics}
\usepackage[pdflatex]{graphicx}
\input{macros-course}


\newif\ifspaceout
\spaceouttrue
%%\spaceoutfalse
\newcommand{\smallspace}{\ifspaceout\vspace{1in}\fi}
\newcommand{\mediumspace}{\ifspaceout\vspace{2in}\fi}
\newcommand{\largespace}{\ifspaceout\vspace{4in}\fi}
\newcommand{\nextproblem}{\ifspaceout\newpage\fi}

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\newcommand{\bij}{\mathbin{\mbox{\rm bij}}}
\newcommand{\inj}{\mathbin{\mbox{\rm inj}}}
\newcommand{\sur}{\mathbin{\mbox{\rm sur}}}
\newcommand{\ran}[1]{\text{range}(#1)}
\newcommand{\Union}{\bigcup}

\newcommand{\eqdef}{\mathbin{\mbox{::=}}}

\newcommand{\ROT}{\mbox{ROT}}
\newcommand{\FBT}{\mbox{FBT}}
\newcommand{\brep}{\mbox{rot-to-fbt}}
\newcommand{\unrep}{\mbox{fbt-to-rot}}
\newcommand{\nil}{\mbox{\texttt{()}}}
\newcommand{\sz}{\mbox{size}}
\newcommand{\cons}{\mbox{cons}}
\newcommand{\sbtr}{\mbox{subtrees}}
\newcommand{\kcomp}[1]{\bar{#1}}

\newcommand{\fins}{\mathcal{F}}

\newcommand{\kpfend}{}

\newcommand{\kskip}[1]{}

\newcommand{\pts}[1]{\relax[#1 points]\enskip\ignorespaces}
\newcommand{\onept}{\relax[1 point]\enskip\ignorespaces}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
   \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\askaboutsolutions

\begin{document}


\ifshowsolutions
{
\begin{center}
{\large \bf
Final Exam Solutions}

\end{center}
\spaceoutfalse
\else
\begin{center}
{\huge \bf
6.042 Final Exam}

Fall 2000
\end{center}

\fi



\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{33} \textbf {Miscellaneous}

Grading: for parts a, c, d, e, give 2 points for each number correctly
circled or correctly left uncircled.  For part b, give 1 point for
each number.

\problempart {\bf (6 points)} Circle the numbers of ALL of the
following which are logical tautologies:

1, 3.

\problempart {\bf (3 points)} Define the relation $R$ such that $nRm$
whenever $n$ and $m$ are natural numbers such that $|n-m|$ is the
square of a natural number (remember that 0 is a natural number).  
Circle the numbers of ALL of the following which apply to $R$:

1, 2.

\problempart {\bf (10 points)} Circle the numbers of ALL of the
following statements that are true for all $m, n > 0 \in N$.  Let $G$
be an $m$ by $n$ grid graph.

2, 3.

\problempart {\bf (8 points)} Circle the numbers of ALL of the
following functions which are $\theta(n)$:

1, 4.

\problempart {\bf (6 points)} Circle the numbers of ALL of the
following which are uncountably infinite sets:

2, 3.

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{16} \textbf {Counting Connected Components of a Graph}

\problempart {\bf (3 points)} If $H$ is the graph given below, and the
edge $(v,w)$ is the one selected in step 2.1, draw the graph $H$ after
step 2.4 in the algorithm.  Label the $z$ vertex in your graph.

Grading:\\ 
1 point for leaving edges not between $v$ or $w$ and some
vertex in the graph.\\
1 point for correctly determining which edges to $z$ belong there.\\
.5 points for labelling $z$ \\
.5 points for removing $v$ and $w$ and their incident edges.\\




\problempart {\bf (3 points)} Model this algorithm as a state machine.

Grading:\\
1 point for having $H$ in the states.\\
.5 points for correct start state.\\
1 point for correct transitions.\\
.5 points for having no transitions when there are no edges.\\


\problempart {\bf (7 points)} Prove, using an invariant, that if the
algorithm terminates, the output is the number of connected components
of $G$.  You may assume that in a graph with no edges, the number of
connected components is equal to the number of vertices.

Grading:\\
1.5 points for formulating an invariant which is sufficient to 
show correctness.\\
4 points for proving the invariant (use normal proof standards).\\
1.5 points for using the invariant to prove correctness (use normal proof
standards).\\

\problempart {\bf (3 points)} Prove that this algorithm always terminates.

Grading:\\
1 point for coming up with a termination function.\\
1 point for proving it is decreasing.\\
1 point for proving it is always a nonnegative integer.\\

\nextproblem


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{9} \textbf {Lines That Cross and Lines That Don't}

Suppose we have a set $L$ of 26 different lines with equations in the
form $y = mx + b$ for real $m$ and $b$.  Prove that there is either

\begin{itemize}
\item[1.]  A set $S$ of 6 lines that never intersect one another when $x>0$, or
\item[2.]  A set $T$ of 6 lines such that any two of them intersect
one another at some point where $x>0$.
\end{itemize}

Hint:  Use Dilworth's Theorem.

Grading:\\ 
9 points for the proof, using normal proof standards, if they DON'T
use Dilworth's theorem.\\
If they do use Dilworths:\\
3 points for coming up with a partial ordering which is sufficient.\\
1 point if they don't have a sufficient partial ordering but they do have
SOME partial ordering on the lines.\\
1 point for proving their relation is a partial order.\\
1 point for finding the value of $t$ that works with Dilworth's Theorem.\\
2 points for proving one of the sets exists if there is a chain\\
2 points for proving the other set exists if there is an antichain

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{10} \textbf {Recurrence Relations}

\problempart {\bf (5 points)}

$$A_n = 1 + n(-1)^n.$$

Grading:\\
1 point for identifying the characteristic polynomial.\\
1 point for factoring the characteristic polynomial.\\
2 points for giving the general form $c_11^n + c_2(-1)^n + c_3n(-1)^n$\\
1 point for solving correctly for $c_1, c_2$, and $c_3$.\\
Give full credit if they get the right answer from some other method.

\problempart {\bf (5 points)} 

$$A_n = (-1)^n + n$$.  

Grading:\\
1 point for giving the general form of the homogenous part.\\
1 point for guessing a particular solution whose FORM is correct. (ie,
$an+b$ or $an^2 + bn + c$.\\
2 points for correctly solving for the coefficients in their particular
solution.\\
1 point for correctly solving for $c_1, c_2$, and $c_3$ given their 
particular solution.\\


\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 5
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{6} \textbf {Summations}

\problempart {\bf (2 points)}  Find a closed form for

$$\sum_{i=0}^{\infty} \sum_{j=1}^n \frac{1}{2^i}$$

Solution: $2n$.

Grading:\\
1 point for the inner sum (it does not depend on $j$).\\
1 point for the geometric sum.\\

\problempart {\bf (4 points)}  Find a closed form for

$$\sum_{i=0}^n (i+1)x^i.$$

Solution:  $$\frac{(n+1)x^{n+2} - (n+2)x^{n+1} + 1}{(x-1)^2}$$

Grading:  If they did the differential method:\\
1 point for getting the upper limit right on  $\sum^{n+1} x^i$ \\
1 point for finding the closed form of this\\
1 point for differentiating correctly\\
1 point for simplifying their answer.

If they looked up solutions:\\
1 point for splitting up the sum into $\sum_{i=0}^n x^i + \sum_{i=0}^n i x^i$\\
1 point for giving the closed form of each part (by lookup)\\
2 points for simplifying their answer.  Yeah, 2 points is a lot but if
the do it this way it's the only thing they have to WORK at.

If they did it some other way:\\
3 points if they give a correct but unsimplified answer.\\
4 points if they give a correct, simplified answer.


\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 6
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{10} \textbf {Combinatorics}
Let $S$ be the set $\{a, b, c, d, e\}$ and let $T$ be the set $\{1,
2, 3, 4\}$. {\bf (2 points each)}

Grading:\\
2 points for a correct answer.\\
1.5 points for an answer that would be correct but was simplified
  incorrectly.\\
1 point for some gross unsimplified mess that might be correct.\\
.5 points for an incorrect answer that shows understanding.
 
\problempart What is the number of binary relations from $S$ to $T$?

Solution: $2^{20} = 1048576$

\problempart What is the number of functions from $T$ to $S$?

Solution: $5^4 = 3125$

\problempart What is the number of injective functions from $T$ to $S$?

Solution: $5! = 120$

\problempart What is the number of surjective functions from $T$ to $S$?

Solution: $0$

\problempart What is the number of surjective functions from $S$ to $T$?

Solution: $2 \cdot 5! = 240$

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 7
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{16} \textbf {Coloring Grid Graphs, Yet Again}

Parts (a) - (d): grading:\\
2 points for a correct answer.\\
1 point for an incorrect answer that shows understanding.

\problempart {\bf (2 points)}  What is Pr$(A)$?  

Solution: $1/4$


\problempart {\bf (2 points)}  What is Pr$(B|A)$?  

Solution: $1/3$

\problempart {\bf (2 points)}  What is Pr$(A|C)$?  

Solution: $1/4$

\problempart {\bf (2 points)}  What is Pr$(B|A \cap C)$?  

Solution: $1/3$

\problempart {\bf (4 points)}  Which pairs of the events $A, B,$ and $C$ are 
independent?  

Solution: $(A,C)$ and $(B,C)$ are independent, $(A, B)$ is not.

Grading:\\
1.5 points for saying that $A$ and $C$ are independent.\\
1.5 points for saying that $B$ and $C$ are independent.\\
1 point for NOT saying that $A$ and $B$ are independent.\\

\problempart {\bf (4 points)}  What is Ex$(X)$?

Solution: $48$

Grading:\\
2 points for setting up variables for each vertex which have simple
expectations to calculate.\\
1 point for correctly expressing $X$ as the sum of these variables.\\
1 point getting the correct expectation for expectation for each variable.\\
4 points for having the correct answer, even if they don't do the
problem this way.

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 8
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{20} \textbf {The Florida Election}

\problempart {\bf (2 points)} Let $X$ be a random variable that
represents the number of votes Gore gets in this county.  What is the
expected value of $X$?

Solution:  6000.

Grading:  No credit for a wrong answer.

\problempart {\bf (3 points)} What is the variance of $X$?

Solution:  2400.

Grading:\\
3 points for a correct answer.\\
1 point for having the formula $V(X) = np(1-p)$ for $n$ independent Bernoulli
trials, but using it incorrectly.\\
.5 points for giving the equation $V(X) = E(X^2) - E(X)^2$ and not being able
to come up with the answer.\\

\problempart {\bf (5 points)} 

Solution:  Pr(...) < $20/21$.

Grading:\\
2 points for having Markov's inequality stated correctly.\\
1 point for substituting $E(X)$ correctly.\\
1 point for having $t$ correct.\\
1 point for having the inequality in the right direction.


\problempart {\bf (5 points)} 

Solution:  (two-sided formula):  Pr(...) < $2/75$ = $2400/90000$

(one-sided formula):  Pr(...) < $2/77$ = $2400/92400$

Either formula is acceptable.

Grading:\\
2 points for having Chebyshev's inequality stated correctly.\\
.5 points for having $E(X)$ correct.\\
1 point for having $V(X)$ correct.\\
1 point for having the correct value of $t$.\\
.5 points if they use the two-sided formula, for saying that
Pr($X - E(X) \geq t) \leq $Pr($|X - E(X)| \geq t)$.\\

\problempart {\bf (5 points)} 

Solution: Pr$(X \geq (21/20)E(X)) \leq e^{-(\ln (21/20) + (20/21) -
1)(21/20)(6000)} = \frac{e^{300}}{(21/20)^{6300}} \approx e^{-7.37803}
\approx .000625$

Grading:\\ 2 points for having Chrenoff's inequality stated
correctly.\\ .5 points for having $E(X)$ correct.\\ .5 points for
having $c$ correct.\\ .5 points for having $\alpha$ correct.\\ .5
points for plugging in the values to get either of the approximate
answers above.

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 9
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{6} \textbf {MIT Football}

Grading: Give credit for any answers that work, not just our solution.

\problempart {\bf (2 points).  Theorem 2}\\ If the numbers on the
jerseys are integers in the set $\{1, \ldots, 100\}$ then the
difference between the numbers on some pair of jerseys is a multiple
of 31.

Pigeons: Jerseys

Pigeonholes:  \underline{Numbers \{0, 1, \ldots, 31\}}

Pigeon $p$ is in hole $h$ if:  \underline{$p \equiv h$ mod $32$}

Grading:\\
1 point per line.


\problempart {\bf (4 points).  Theorem 3}\\ If the numbers on the
jerseys are integers in the set $\{1, \ldots, 100\}$ then if the
jerseys are lined up in ascending order by their numbers, there is a
nonempty consecutive subset of the jerseys whose numbers add up to a
multiple of 32.

Pigeons: \underline{Sum of the first $i$ jerseys}

Pigeonholes:  \underline{Numbers \{0, 1, \ldots, 31\}}

Pigeon $p$ is in hole $h$ if:  \underline{$p \equiv h$ mod $32$}

Grading:\\
2 points for the Pigeons,
1 point each for the other two lines.


\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 10
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{6} \textbf {Die Rolling}

Say you roll a fair 6-sided die.  If you get a 6, you may roll again,
and add 6 to the outcome; if you roll multiple 6's in a row, you
continue to roll again.  So, for example, if you roll a 6 and then a
5, the outcome is 11; if you roll a 6, then a 6, then a 6, then a 2,
the outcome is 20.

What is the expected value of the outcome?  

Solution: $\frac{21}{5}$

Grading:\\
Full points for a correct answer.\\
4 points for a correct answer in non-closed form.\\
If they do this with Wald's theorem:\\ 
2 points for correctly setting up $Q$ (number of die rolls) and 
$R_i$ (value of each die roll)\\
1 point for correctly calculating Ex($R_i) = 7/2$\\
2 points for correctly calculating Ex($Q) = 6/5$\\
1 point for multiplying Ex($R_i)$Ex($Q)$ to get their answer.\\


\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 11
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{10} \textbf {Chess Matches}

Math Moose and Theory Pig have been playing a series of chess games,
and have noticed a number of facts:

\begin{itemize}
\item  Math Moose wins any given game with probability 8/17.
\item If Math Moose wins, he is equally likely to have played either
white or black.
\item If Math Moose loses, then with probability 8/9, he played black.
\item If Math Moose plays white, he always takes Theory Pig's queen at some point in the game.
\item If Math Moose plays black and wins, he takes Theory Pig's queen with probability 1/2.
\item If Math Moose plays black and loses, he takes Theory Pig's queen with probability 1/4.
\end{itemize}

\problempart {\bf (4 points)} Define the sample space, and give the
probability associated with each outcome.

Solution:\\
Math Moose plays white, wins, and takes Theory Pig's queen: $4/17$\\
Math Moose plays white, loses, and takes Theory Pig's queen: $2/17$\\
Math Moose plays white, loses, and doesn't take the queen: $2/17$\\
Plays black, wins, and takes: $1/17$\\
Plays black, loses, and takes: $2/17$\\
Plays black, loses, and doesn't take: $6/17$\\

Grading:\\
4 points if they get all these cases with correct probabilities\\
If they draw a tree:\\
2 points for drawing the tree with the decisions in the right order
(white/black, then win/loss, then take/don't take).\\
.5 points for getting the probabilities right at each of the three levels.\\
.5 points for multiplying to get the probability for each case.\\
If they draw a Venn Diagram:\\
.5 points for each of the eight regions (including the two regions which are
empty)\\

\problempart {\bf (3 points)} What is the probability that Math Moose
wins a random game in which he plays white?

Solution: 4/5.

Grading:\\
3 points for answering 4/5.\\
1 point for answering 4/17 (the probability he wins and plays white)\\


\problempart {\bf (3 points)} What is the probability that Math Moose
wins a random game, given that he takes Theory Pig's queen?

Solution:  5/9.

Grading:\\
3 points for answering 5/9.\\
1 point for answering 5/17.\\

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 12
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{8} \textbf {Overloading Circuits}

\problempart {\bf (5 points)} Express the expected number of memory
cells that burn out in a power surge, in terms of $p$.  (Hint: use
linearity of expectation.)

Solution: $\frac{1}{1-p}$.

Grading: If they use the linearity of expectation method:\\
1 point for expressing the desired variable $X$ in terms of the sum of
indicator variables.\\
2 points for determining the probability of the indicator variables being 1.\\
2 points for summing the probabilities.  The answer need NOT be in
closed form; if it's not it'll bite them in the butt on part (b).\\
If they use some other method:\\
3 points for having some formula for expectation which is true (ie
Ex$(X) = \sum_{s \in S} s $Pr$(X = s)$)\\
2 points for plugging in the right things.\\

\problempart {\bf (3 points)} It is discovered
that the mean number of memory cells that burn out from a power surge is
10.  What is $p$?

Solution: $9/10$.

Grading:\\ 3 points if they get $9/10$.  \\1 point if their answer for
part (a) was incorrect but they solved for $p$ correctly.


\end{problems}
\end{document}
