\documentstyle[psfig,fullpage,12pt]{article}

\newcounter{problem}

\newenvironment{problems}{\begin{enumerate}\setcounter{enumi}{\theproblem}}{\setcounter{problem}{\theenumi}\end{enumerate}}

\pagestyle{empty}


% magic for a Postscript figure:
%
%\begin{figure}[h]
%\centerline{\psfig{file=,width=}}
%\caption{}
%\end{figure}

\begin{document}

{\large
\fbox{\parbox{6.1in}{
\hbox to \hsize{\ \ \ 10 Powerful Ideas  \hfil 
Bruce Maggs}
\vskip 0.1in
\hbox to \hsize{\ \ \ Final Review Exercises \hfil Final Exam: {\bf Monday, May 4, 1998}}
\vskip 0.1in
\hbox to \hsize{ \hfil {\bf 1pm-4pm, DH2210}}
}}}
\vskip 0.1in

%\setlength{bigskipamount}{3in}

\section*{Quickies}
\begin{problems}

\item
\[\sum_{i=0}^{n} 2^i = \]

\item
\[\sum_{i=0}^{n} x^i = \]

\item
\[\sum_{i=0}^{n} i = \]

\item
\[\sum_{i=0}^{n} {n \choose i} = \]

\item
\[{n \choose i-1} + {n \choose i} = \]

\item
What is the coefficient of $a^2b^3c^5$ in $(a+b+c)^{10}$?

\end{problems}

\section*{Induction}
\begin{problems}


\item
Solve the following recurrences:

\begin{enumerate}
\item
\begin{eqnarray*}
T(n) & = & 6T(n-1) - 8T(n-2) \\
T(0) & = & 0 \\
T(0) & = & 1
\end{eqnarray*}

\item
\begin{eqnarray*}
T(n) & = & 2T(n/2) + n^2 \\
T(1) & = & 1
\end{eqnarray*}
\end{enumerate}

\item
Prove by induction that $\phi^n = F_n \phi + F_{n-1}$ for $n \geq 1$.


\end{problems}


\section*{Groups and Fields}
\begin{problems}

\item
State the four properties that define a group.

\item
List all the subgroups of $({\cal Z}_p, +)$, where $p$ is prime.

\item
Prove that the set of $n$-bit bitstrings is a group under the operation bitwise XOR.

\item
Prove that the set of $n$-bit bitstrings with even parity is a
subgroup of the group in the previous problem.

\item
Show that the set of complex numbers $a+bi$ is a field.


\end{problems}


\section*{Counting and Probability}
\begin{problems}

\item
The numbers 1447, 1005, and 1231 have something in common: each is a
4-digit number beginning with 1 that has exactly two identical digits.
How many such numbers are there?

\item
What is the largest 2-digit prime factor of the integer $n = {200
\choose 100}$?

\item 
Letters in Morse code are formed by a succession of dots and dashes with
repetitions allowed. How many different letters could be represented by $10$ or fewer
dots and dashes?

\item 
$n$ balls are placed randomly into $n$ cells. What's the probability that
exactly one cell remains empty? 

\item
A fair coin is flipped $n$ times.  What's the probability that all the heads occur at the
end of the sequence?

%\item
%What's the probability that if I pick $n \ge 365$ people at random, all
%possible birthdays will be represented (ignoring leap years).

\item
A box contains $90$ good and $10$ defective screws. What's the probability that
if $10$ screws are used, none will be defective?

\item 
What is 
$${{n\choose 0}} - {{n\choose 1}} + {{n \choose 2}} - {{n \choose 3}} \ldots$$
and why?

\item 
What is $(x+y+z)^m$ as a sum of terms?

\item
True or false: 
\begin{enumerate}
\item
$E[AB] = E[A]E[B]$ if and only if $A$ and $B$ are
independent.

\item
$E[A+B] = E[A] + E[B]$ if and only if $A$ and $B$ are
independent.

\item
$E[log A] = log E[A]$ for all random variables $A$.
\end{enumerate}

\item
What is the probability of rolling two pair (such as 5 5 3 3 6) on the first roll 
in Yahtzee?

\item
What is the probability of getting two pair (such as Q Q A A 3) in poker?

\item
If you choose a $k$-bit number by randomly picking bits, what is the probability of
getting a power of 2?

\item
If you pick a $k$-bit number at random, what is the probability of
picking a prime?

\item
What is $90^{1584} \pmod{11}$? (Hint: use Fermat's Little Theorem)

\item
Give two proofs for the identity
$${n \choose 0} + {n \choose 1} + \cdots + {n \choose n} = 2^n$$
One proof should be algebraic (manipulating symbols), the other combinatoric (showing a
correspondence between two sets).

\item
If you pick two socks at random from a drawer with 5 gray socks and 4
black socks, what is the probability that the two socks match?

% Answer: 5/9*4/8 + 4/9*3/8 = 32/72
% Alternatively: ({5 \choose 2} + {4 \choose 2}) / {9 \choose 2})

\item
What is the probability that, out of $n$ people chosen at random, at least two have the 
same birthday?

\item
How many people must you choose at random in order to ensure that at least {\em ten} people 
have the same birthday (ignore leap years)?

\end{problems}


\section*{Infinities, Undecidability, Intractability, Languages}
\begin{problems}

\item
Give an example of each of the following, or explain why it don't exist.

\begin{enumerate}
\item
a countably infinite field

\item
a finite group

\item
an uncountable regular language

\item
a one-to-one onto function from $\cal{N}$ to $\cal{R}$.

\end{enumerate}


\end{problems}


\section*{Graph Theory}
\begin{problems}

\item
How many different Hamiltonian cycles are possible in a labeled
complete graph on $n$ vertices?

\item
How many trees can be made with 10 labeled nodes and 10 edges?

\end{problems}

\section*{A Moment's Thought}

\begin{problems}
\item
For $\{1,2,3,\ldots,n\}$ and each of its nonempty subsets a unique
{\em alternating sum} is defined as follows: Arrange the numbers in
the subset in decreasing order and then, beginning with the largest,
alternately add and subtract successive numbers.  (For example, the
alternating sum for $\{1,2,4,6,9\}$ is $9-6+4-2+1 = 6$ and for $\{5\}$
it is simply 5.)  Find the sum of all such alternating sums for $n=7$.

\item
Imagine constructing a graph as follows. Draw $10$ nodes. Then for each
pair of nodes, draw an edge between them with probability $p$. What is the
expected number of nodes with degree exactly two? 

\end{problems}

\end{document}
