\documentstyle[12pt,psfig]{cmu-art}
%\setlength{\textwidth}{6.50in}
%\addtolength{\oddsidemargin}{-0.75in}
%\addtolength{\evensidemargin}{-0.75in}
%\topmargin -1in
\begin{document}
\centerline{\psfig{figure=tpi.eps,height=1.0in,width=4.0in}}
{\large
\fbox{\parbox{6.1in}{
\hbox to \hsize{\ \ \ Final Exam Solutions \hfil Bruce Maggs \hfil May 4, 1998\ \ \ }

\vskip 0.1in
}}}


\newcommand{\problem}[4]{\noindent {\bf #1}. [#2 points] {\bf #3.} \\ {\small {\it #4 }}}

\newcommand{\wisdom}[2]{\begin{quotation}
 \begin{center} \bf #1 \end{center} #2 \end{quotation} }

\wisdom{Repeat After Me.}{This part is to test your ability to study 
material and repeat it.
}

\problem{1}{3}{Contrapositive}
{
What is the contrapositive of the assertion ``$A$ implies $B$''?
}

\begin{centering}
not $B$ implies not $A$
\end{centering}



\problem{2}{3}{Geometric series}
{Give a closed-form expression for $\sum_{i=0}^{+\infty} x^i$, where
$|x| < 1$.}

$$1 \over 1-x$$

\problem{3}{3}{Group size}
{State {\it Lagrange's Theorem}.}

For any group $G$ and subgroup $H$ of $G$, $|H|$ divides $|G|$.

\problem{4}{3}{Polynomial interpolation}
{In the finite field $GF_p$, how many degree-$(n-1)$ polynomials pass
through the $k$ points $(x_1,y_1), (x_2,y_2), (x_3,y_3), \ldots, (x_k,y_k)$?
(Assume $k \leq n$.)}

Since $n$ points determine a degree-$(n-1)$ polynomial, you can choose
the remaining $n-k$ points arbitrarily.  Each point has $p$ choices,
so there are $p^{n-k}$ polynomials.  (Note that this answer also
assumes that $n \leq p$; otherwise you won't be able to find $n$
distinct points $x_i$ to determine the polynomial.)

\problem{5}{3}{One-to-one function}
{
Let $f$ be a function from a set $A$ to a set $B$.  Give a necessary
and sufficient condition for $f$ to be a {\it one-to-one\/} function.
}

For all $x$ and $y$ such that $x \neq y$, $f(x) \neq f(y)$.

\problem{6}{3}{The halting problem}
{
Give an example of a real number that is describable but not computable.
}

The real number between 0 and 1 whose decimal representation is
defined as follows: the $i$th digit after the decimal point is 1 if
the $i$th computer program halts when run on a description of itself,
and 0 otherwise.  If a program existed to compute the digits of this
number, then you could use it to solve the halting problem.

\problem{7}{3}{Finite probability space}
{Suppose that $\Omega$ is a finite set of {\it outcomes\/} and that
$p$ is a function from subsets of $\Omega$ (called {\it events}) to
real numbers in the range $[0,1]$.  What two conditions must $p$
satisfy in order for $\Omega$ and $p$ together to form a probability
space?}

\begin{enumerate}
\item $p(\Omega) = 1$
\item For all $E \subseteq \Omega$, 
$$p(E) = \sum_{\omega \in E} p({\omega})$$
\end{enumerate}

\problem{8}{3}{Fermat's Little Theorem}
{
State {\it Fermat's Little Theorem}.
}

For any prime $p$ and $1 \leq a \leq p-1$,
$$a^{p-1} \equiv 1 \pmod{p}$$


\problem{9}{3}{Big-Omega notation}
{Suppose that $f$ and $g$ are both functions from the natural numbers
to the natural numbers.  Give a precise definition of the notation
$f(n) = \Omega(g(n))$.
}

There exists $c > 0$ and $N \geq 0$ such that for all $n \geq N$,
$$f(n) \geq cg(n)$$

\problem{10}{3}{Field} {The following definition of a field has one
mistake in it.  What is the mistake?  A set $S$ together with an
addition operator $\oplus$ and a multiplication operator $\odot$ form
a {\it field\/} if $S$ and $\oplus$ form a commuative group, $S$ and
$\odot$ form a commutative group, and $\odot$ distributes over
$\oplus$.}

$S - {0}$ and $\odot$ form a commutative group (not $S$ and $\odot$),
where 0 is the identity element of $\oplus$.

\newpage

\problem{11}{5}{Horner's method}
{ Suppose that the $n$ coefficients of a degree $n-1$ polynomial $p(x)
= a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + \cdots + a_0$ are stored in an
array $a$, so that the coefficient of $x^i$ in $p(x)$ is $a[i]$.
Write a piece of C or C++ code to evaluate $p$ at some point $x = b$, i.e.,
evaluate $p(b)$.  Ignoring calculations of loop indices, your program
must perform at most $n-1$ additions and $n-1$ multiplications.
}

Ignoring variable declarations,
\begin{verbatim}
p = a[n-1];
for (i=n-2; i >= 0; i--)
    p = x*p + a[i];
return p;
\end{verbatim}

\problem{12}{5}{Euclid's algorithm}
{ Given two non-negative integers $a$ and $b$, where $b \geq a$,
Euclid's algorithm finds the greatest common divisor of $a$ and $b$.
Give a short recursive description of Euclid's algorithm (in
pseudocode or C/C++).  }

\begin{verbatim}
gcd (a, b)
    if a = 0 then return b
    else return gcd (b mod a, a)
\end{verbatim}


\wisdom{Basic Techniques.}{This part will test your ability to reason with some
of the basic techniques learned in the class. 
}

\problem{13}{8}{Recurring nightmares}
{Give a closed-form solution to the following recurrence.  Show your
work.
\begin{eqnarray*}
f(n) & = & 5f(n-2) - 4f(n-4) \\
f(0) & = & 2 \\
f(1) & = & 0 \\
f(2) & = & 8 \\
f(3) & = & 0 \\
\end{eqnarray*}
}

Try $f(n) = \lambda^n$:
\begin{eqnarray*}
\lambda^n  = 5 \lambda^{n-2} - 4 \lambda^{n-4} \\
\lambda^{n-4} (\lambda^4  - 5 \lambda^2 + 4) & = & 0 \\
\lambda^{n-4} (\lambda^2  - 4) (\lambda^2 - 1) & = & 0 \\
\lambda^{n-4} (\lambda  - 2) (\lambda  + 2) (\lambda - 1) (\lambda + 1) & = & 0
\end{eqnarray*}

So the possible solutions are $2^n, (-2)^n, 1^n, (-1)^n$.\\
Try $f(n) = a2^n + b(-2)^n + c1^n + d(-1)^n$:
\begin{eqnarray*}
f(0) = a + b + c + d & = & 2 \\
f(1) = 2a - 2b + c - d & = & 0 \\
f(2) = 4a + 4b + c + d & = & 8 \\
f(3) = 8a - 8b + c - d & = & 0
\end{eqnarray*}

Solving for the unknowns gives:
\begin{eqnarray*}
a & = & 1 \\
b & = & 1 \\
c & = & 0 \\
d & = & 0
\end{eqnarray*}

So the answer is
$$f(n) = 2^n + (-2)^n$$


\problem{14}{8}{Seven-card stud}
{{\it Seven-card stud\/} is a variation of poker in which each player
is dealt seven cards, and then selects any five of the seven to form a
poker hand.

How many times more likely is it to receive a hand containing
four-of-a-kind in seven-card stud than in the version of poker in
which each player is dealt five cards and cannot discard or exchange
any cards?  (We're looking for the ratio of the probabilities.)}
\begin{eqnarray*}
\Pr(\mbox{4 of a kind in 5-card stud}) &=& {13 \cdot 48 \over {52 \choose 5}} \\
\Pr(\mbox{4 of a kind in 7-card stud}) &=& {13 \cdot {48 \choose 3} \over {52 \choose 7}}
\end{eqnarray*}

\begin{eqnarray*}
{\Pr(\mbox{4 of a kind in 7-card stud}) \over \Pr(\mbox{4 of a kind in 5-card stud}) } &=& {{13 \cdot {48 \choose 3} \over {52 \choose 7}} \over {13 \cdot 48 \over {52 \choose 5}} } \\
& = & { {48 \choose 3} {52 \choose 5} \over 48 {52 \choose 7} } \\
& = & { {48 \cdot 47 \cdot 46 \over 3 \cdot 2} {52 \cdot 51 \cdot 50 \cdot 49 \cdot 48 \over 5 \cdot 4 \cdot 3 \cdot 2} \over 48 {52 \cdot 51 \cdot 50 \cdot 49 \cdot 48 \cdot 47 \cdot 46 \over 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2} } \\
& = & 7
\end{eqnarray*}


\problem{15}{8}{Even worse than taking this final}
{Four graders have 112 final exams to grade.}

\begin{enumerate}

\item {\small {\it (4 points) How many different ways are there of dividing up the 112 exams
among the 4 graders? (We don't care if some graders get more work than
others.)}}

Each exam can be assigned to any grader independently,
$$4^{112} \mbox{ ways}$$


\item {\small {\it (4 points) Suppose that the graders are not concerned with the names of the
students on the exams that they are to grade, but only about the
number of exams that they are to grade.  How many different ways are
there of partitioning the exams when they are all indistinguishable
(again, not caring if some graders get more work than others)?}}

Rearrange the 112 identical exams with $4-1 = 3$ identical separators,
$${115 \choose 3} \mbox{ ways}$$

\end{enumerate}


\wisdom{A Moment's Thought!}{This section tests your ability to think a little
bit more insightfully. You must give complete explanations of your answers.
{\bf Do three of the five problems. Do not do all five; if you do we will
grade three of our choice.} }

\problem{16}{12}{We really do think like this}
{Prof.\ Baraff and Prof.\ Maggs are competing to see who can give
harder homework assignments.  For each assignment, Prof.\ Maggs wins
with probability 1/2 and Prof.\ Baraff wins with probability 1/2,
independent of the outcomes of the previous assignments.  The
competition ends when one of these (admittedly somewhat evil)
professors has won on two more of the assignments than the other one.
At this point the professors stop giving out assignments.
How many 15-299 assignments do you expect to have to do?

{\em Hint: Look at two assignments at a time.}}

Consider the possible outcomes of each pair of assignments (where $B$
represents a win by Baraff and $M$ represents a win by Maggs): $BB$,
$MM$, $BM$, and $MB$, each with probability $1/4$.  As long as $BM$ or
$MB$ occur (probability $1/2$), the score is tied and the game keeps
going.  As soon as $BB$ or $MM$ occurs (probability $1/2$), the game
is over.  The expected number of pairs of assignments needed for a
$BB$ or $MM$ to appear is 2, so the expected number of assignments is
4.

\problem{17}{12}{Defying all expectations}
{Provide a counterexample to the following hypothesis.

\noindent{\it Hypothesis.} For every finite probability space and
every random variable $x$ defined on that probability space, for any
function $f$ mapping the reals to the reals, $$E[f(x)] = f(E[x]). $$

Give a counterexample (a random variable $x$ and a function $f$ that
falsify the hypothesis) and show why. }

Let $f(x) = 2^x$ and $x$ be the random variable which is 0 with
probability $1/2$ and 1 with probability $1/2$.  Then
\begin{eqnarray*}
E[f(x)] & = & {1 \over 2}\cdot 2^0 + {1 \over 2}\cdot 2^1 = {3 \over 2} \\ 
f(E[x]) & = & f({1 \over 2}\cdot 0 + {1 \over 2}\cdot 1) = f({1 \over 2}) = 2^{1 \over 2} = \sqrt{2}
\end{eqnarray*}

Thus $E[f(x)] \neq f(E[x])$.

\problem{18}{12}{Sign on the dotted line}
{In the RSA public-key cryptography system, a plaintext message $m$
from Bob to Alice is encrypted using Alice's public key $\langle e,n
\rangle$ by computing $m^e \, \mbox{\rm mod} \, n$.  Alice, who has a
private key $d$ such that $e \cdot d = 1 \, \mbox{\rm mod} \,
\phi(n)$, then decrypts the message by computing $\left(m^e\right)^d =
m^{ed} = m \, \mbox{\rm mod} \, n$.

One drawback to the scheme, as described so far, is that there is no
way for Alice to tell if the message really was sent by Bob, or if it
was forged by an imposter.  To remedy this problem, a signature scheme
is used.  Suppose that Bob's public key is $\langle e',n' \rangle$,
and his private key is $d'$, such that $e' \cdot d' = 1 \, \mbox{\rm
mod} \, \phi(n')$. Rather than sending $m^e$ to Alice, Bob sends
$(m^{d'} \mbox{\rm mod}\, n')^e \, \mbox{\rm mod} \, n$.}

\begin{enumerate}

\item {\small {\it (4 points) Explain how Alice recovers the original plaintext message $m$.}}

She applies her private key $d$ to get $((m^{d'} \mbox{\rm mod}\,
n')^e)^d \, \mbox{\rm mod} \, n = m^{d'} \mbox{\rm mod}\, n'$.  Then
she applies Bob's public key $e'$ to get $(m^{d'})^{e'} \mbox{\rm
mod}\, n' = m$.

\item {\small {\it (4 points) Why can Bob be confident that revealing both $m$ and
$m^{d'} \, \mbox{\rm mod} \, n'$ to Alice is a safe thing to do? {\em
Hint: How can Alice generate a similar pair of numbers $x$ and $x^{d'} \, \mbox{\rm mod} \, n'$ by
herself, using only public information?}}}

Bob might be worried that revealing $m$ and $m^{d'} \, \mbox{\rm mod}
\, n'$ to Alice might give her the ability to figure out his private
key $d'$.  Here's why she can't.  Suppose Alice had a procedure that
used the pair $x$ and $x^{d'} \, \mbox{\rm mod} \, n'$ to compute
$d'$.  Then she could take any number $y$ and compute $y^{e'} \,
\mbox{\rm mod} \, n'$ to form a pair suitable for this procedure
(where $x = y^{e'} \, \mbox{\rm mod} \, n'$ and $x^{d'} =
(y^{e'})^{d'} \, \mbox{\rm mod} \, n' = y$).  So if she had such a
procedure, she would be able to get Bob's private key by herself!  Bob
isn't revealing anything new.

\item {\small {\it (4 points) Why is Alice confident that the message $(m^{d'}) \, \mbox{\rm
mod} \, n'$ was encrypted by Bob and not by someone else?}}

Only someone who knows $d'$ can compute $(m^{d'}) \, \mbox{\rm mod} \,
n'$.  Since only Bob knows $d'$, the message must have been encrypted
by Bob.

\end{enumerate}


\problem{19}{12}{That's irrational}
{A real number is called {\it rational\/} if it can be expressed as the
ratio of two integers, and {\it irrational\/} otherwise.  In solving
this problem, you may assume that $\sqrt{2}$ is irrational.  (It is.)}

\begin{enumerate}

\item {\small {\it (4 points) Prove that if $x$ is a rational number, then $x \cdot \sqrt{2}$
is an irrational number.}}

This statement is actually true only if you exclude $x=0$, so we'll do
that in our proof.
 
Proof by contradiction.  Suppose for some rational $p \over q$, ${p
\over q}
\cdot \sqrt{2}$ is a rational number $p' \over q'$.  Then $\sqrt{2} = {p' q \over q' p}$, so $\sqrt{2}$ is rational.  This is a contradiction, so ${p \over q}
\cdot \sqrt{2}$ must be irrational for all $p \over q$.


\item {\small {\it (4 points) Let $Q$ denote the set of rational numbers, and let $T$ denote
the set of numbers that are rational multiples of $\sqrt{2}$, i.e., $T
= \{y: y = x \cdot \sqrt{2}, \,x \in Q\}$.  Prove that there is a
one-to-one and onto mapping from $Q \cup T$ to $T$.}}

The rational numbers $Q$ are countable.  $T$ is also countable,
because $f(x) = x \cdot \sqrt{2}$ is a one-to-one onto mapping from
$Q$ to $T$.  So we can enumerate both $Q$ and $T$.  We can enumerate
$Q \cup T$ by interleaving the enumerations for $Q$ and $T$ (including
$0$ only once, however), so $Q \cup T$ is countable.  Since both $T$
and $Q \cup T$ are countable, there must be a one-to-one onto mapping
from $Q \cup T$ to $T$.

\item {\small {\it (4 points) Prove that the set of real numbers has the same cardinality as
the set of irrational numbers. {\em Hint: divide the real numbers into
$Q \cup T$ and ${\cal R} - (Q \cup T)$.}}}

Form a one-to-one onto mapping from the reals to the irrationals as
follows.  Map elements in $Q \cup T$ (the rationals, and all
irrationals that are rational multiples of $\sqrt{2}$) to their
corresponding elements in $T$ according to the one-to-one onto mapping
from part (b).  Map elements in ${\cal R} - (Q \cup T)$ (the
irrationals that are {\em not} rational multiples of $\sqrt{2}$) to
themselves.  Putting these two one-to-one onto functions together
covers all the irrational numbers.  Thus the reals have the same
cardinality as the irrationals.

\end{enumerate}


\problem{20}{12}{Hypercubic}
{The {\it hypercube} of dimension $k$, abbreviated $H_k$,
is a graph that can be constructed recursively by making two copies of
$H_{k-1}$ and joining corresponding nodes in the two copies
by an edge.  For the base case, $H_0$ is a single node.  The hypercube
$H_4$ is shown below.}

\begin{figure}[h]
\centerline{\psfig{file=hypercube2.ps,height=3in}}
\end{figure}

\begin{enumerate}

\item {\small {\it (6 points) Prove by induction that $H_k$ has $k2^{k-1}$ edges.}}

First we need a lemma: the number of nodes in $H_k$ is $2^k$.  By
induction on $k$: $H_0$ has $2^0 = 1$ node.  If $H_{k-1}$ has
$2^{k-1}$ nodes, then since $H_k$ consists of two copies of $H_{k-1}$
with no other nodes added, $H_k$ has $2 \cdot 2^{k-1} = 2^k$ nodes.

Now to prove that $H_k$ has $k2^{k-1}$ edges, again by induction on
$k$.  For the base case, observe that $H_0$ has $0 \dot 2^{0-1} = 0$
edges.  Now suppose $H_{k-1}$ has $(k-1)2^{k-2}$ edges.  The hypercube
$H_k$ consists of two copies of $H_{k-1}$ with edges added between
corresponding nodes, so $H_k$ has $2 \cdot (k-1)2^{k-2} + 2^{k-1} =
(k-1)2^{k-1} + 2^{k-1} = k2^{k-1}$ edges, as desired.

\item {\small {\it (6 points) Prove that for all $k \geq 2$, $H_k$ has a Hamiltonian tour.
(Recall that a {\it Hamiltonian tour\/} is a simple cycle that visits
all of the nodes in a graph.)}}

By induction on $k$, as before.  The base case is $H_2$ (four nodes
arranged in a square), which has a trivial Hamiltonian tour.

Now suppose $H_{k-1}$ has a Hamiltonian tour.  The hypercube $H_k$
consists of two copies of $H_{k-1}$ with corresponding vertices
joined.  Let us denote these $H_{k-1}$ subgraphs by $H_{k-1}$ and
$H_{k-1}'$.  To make a Hamiltonian tour of $H_k$, start at any node
$x$ in $H_{k-1}$ and follow the Hamiltonian tour of $H_{k-1}$.  At the
last node $y$ of the tour, just before returning to $x$, move to the
corresponding node $y'$ in the other subgraph $H_{k-1}'$.  Follow the
Hamiltonian tour of $H_{k-1}'$ backwards through corresponding nodes
to reach $x'$, then move back to its corresponding node $x$,
completing the tour.  Because the Hamiltonian tours of $H_{k-1}$ and
$H_{k-1}'$ visit every node in their respective subgraphs exactly
once, the overall tour visits every node in $H_k$ exactly once.

\end{enumerate}

% \vspace*{1in}
%
% \item How many different 3-vertex paths are contained in
% $Q_k$?

% On part (c) of the hypercube problem (number of 3-vertex paths in 
% Q_k), I believe it may be too much to ask for a closed form, so
% a recurrence relation shouls suffice.

% >How many different 3-vertex paths  {figure}  are contained in
% >$Q_k$?

% Solution: By inspection there are 0 3-vertex paths in Q_0 and Q_1.  
% We consult the inductive definition of Q_k to count the
% general case.  Q_k contains all the 3-vertex paths contained entirely
% within each of the two Q_k-1 components, plus paths that contain one
% of the "bridge" edges.  For each edge in each Q_k-1 component there
% are 2 "bridge" paths, one for each vertex it is incident upon.  From
% part (a), we know that $Q_k$ has $k2^{k-1}$ edges.  We get the
% following recurrence, where P(k) is the number of 3-vertex paths in
% Q_k:
%
%     P_0 = P_1 = 0
%   
%     P_k = 2 * P_k-1  +  2 * 2 * (k-1) * 2^(k-2)
%
%         = 2 * P_k-1  +  (k-1) 2^k
%
% (This checks for P_2 = 4)



\end{document}


