\Question{Error-Correcting Codes}
\begin{enumerate}
\renewcommand{\labelenumi}{(\alph{enumi})}
\item
Recall from class the error-correcting code for erasure errors, which
protects against up to $k$ lost packets by sending a total of $n+k$ packets
(where $n$ is the number of packets in the original message). Often the number
of packets lost is not some fixed number $k$, but rather a \emph{fraction} of
the number of packets sent. Suppose we wish to protect against a fraction
$\alpha$ of lost packets (where $0 < \alpha < 1$). At least how many packets do
we need to send (as a function of $n$ and $\alpha$)?
\item
Repeat part (a) for the case of general errors.
\end{enumerate}
\Question{Polynomials in One Indeterminate}
We will now prove a fundamental result about polynomials: every non-zero
polynomial of degree $n$ (over a field $F$) has at most $n$ roots. If
you don't know what a field is, you can assume in the following that
$F = \mathbb{R}$ (the real numbers).
\begin{Parts}
\Part Show that for any $\alpha \in F$, there exists some polynomial $Q(x)$
of degree $n-1$ and some $b \in F$ such that $P(x) = (x-\alpha)Q(x) + b$.
\Part Show that if $\alpha$ is a root of $P(x)$, then $P(x) =
(x-\alpha)Q(x)$.
\Part Prove that any polynomial of degree $1$ has at most one
root. This is your base case.
\Part Now prove the inductive step: if every polynomial of degree
$n-1$ has at most $n-1$ roots, then any polynomial of degree $n$ has
at most $n$ roots.
\end{Parts}
\Question{Properties of $\GF(p)$}
\begin{Parts}
\Part Show that, if $p(x)$ and $q(x)$ are polynomials over the
reals (or complex, or rationals) and $p(x)\cdot q(x) = 0$ for all
$x$, then either $p(x)=0$ for all $x$ or $q(x)=0$ for all $x$ or both.
(\textit{Hint}: You may want to prove first this lemma, true in all fields:
The roots of $p(x)\cdot q(x)$ is the union of the roots of $p(x)$ and $q(x)$.)
\Part Show that the claim in part (a) is false for finite fields $\GF(p)$.
%Show that, in contrast, in $GF(p)$ there are two nonzero polynomials whose product is zero. (A polynomial $p(x)$ is non-zero if $p(x)\neq 0$ for some (but not necessarily all) $x$.) ({\em Hint:} Fermat's little Theorem is useful here.)
\end{Parts}
\Question{Poker Mathematics}
A \emph{pseudo-random number generator} is a way of generating a large quantity of random-looking numbers, if all we have is a little bit of randomness (known as the \emph{seed}). One simple scheme is the \emph{linear congruential generator}, where we pick some modulus $m$, some constants $a,b$, and a seed $x_0$, and then generate the sequence of outputs $x_0,x_1,x_2,x_3,\dots$ according to the following equation:
\[
x_{t+1} = ax_t + b \pmod m
\]
(Notice that $0 \le x_t < m$ holds for every $t$.)
You've discovered that a popular web site uses a linear congruential generator to generate poker hands for its players. For instance, it uses $x_0$ to pseudo-randomly pick the first card to go into your hand, $x_1$ to pseudo-randomly pick the second card to go into your hand, and so on. For extra security, the poker site has kept the parameters $a$ and $b$ secret, but you do know that the modulus is $m=2^{31}-1$ (which is prime).
Suppose that you can observe the values $x_0$, $x_1$, $x_2$, $x_3$, and $x_4$ from the information available to you, and that the values $x_5,\dots,x_9$ will be used to pseudo-randomly pick the cards for the next person's hand. Describe how to efficiently predict the values $x_5,\dots,x_9$, given the values known to you.
\Question{Secret Sharing with Spies}
An officer stored an important letter in her safe. In case she is
killed in battle, she decides to share the password (which is a number)
with her troops. However, everyone knows that there are 3 spies among
the troops, but no one knows who they are except for the three spies
themselves. The 3 spies can coordinate with each other and they will
either lie and make people not able to open the safe, or will open the
safe themselves if they can. Therefore, the officer would like a
scheme to share the password that satisfies the following conditions:
\begin{itemize}
\item When $M$ of them get together, they are guaranteed to be
able to open the safe even if they have spies among them.
\item The 3 spies must not be able to open the safe all by themselves.
\end{itemize}
Please help the officer to design a scheme to share her password. What
is the scheme? What is the smallest $M$? Show your work and argue why
your scheme works and any smaller $M$ couldn't work.
\Question{Berlekamp-Welch Algorithm}
In this question we will go through an example of error-correcting codes with
general errors. We will send a message $(m_0,m_1,m_2)$ of length $n = 3$.
We will use an error-correcting code for $k = 1$ general error, doing
arithmetic modulo $5$.
\begin{Parts}
\renewcommand{\labelenumi}{(\alph{enumi})}
\Part Suppose $(m_0,m_1,m_2) = (4,3,2)$. Use Lagrange interpolation to
construct a polynomial $P(x)$ of degree $2$ (remember all arithmetic is $\bmod
5$) so that $(P(0),P(1),P(2)) = (m_0,m_1,m_2)$. Then extend the message to
length $n+2k$ by appending $P(3),P(4)$. What is the polynomial $P(x)$ and
what is the message $(c_0,c_1,c_2,c_3,c_4) = (P(0),P(1),P(2),P(3),P(4))$ that
is sent?
\Part Suppose the message is corrupted by changing $c_0$ to $0$. We will
locate the error using the Berlekamp-Welch method. Let $E(x) = x + b_0$ be
the error-locator polynomial, and $Q(x) = P(x)E(x) = a_3x^3 + a_2x^2 + a_1x +
a_0$ be a polynomial with unknown coefficients. Write down the system of
linear equations (involving unknowns $a_0,a_1,a_2,a_3,b_0$) in the
Berlekamp-Welch method. You need not solve the equations.
\Part The solution to the equations in part (b) is $b_0 = 0, a_0 = 0, a_1 = 4,
a_2 = 4, a_3 = 0$. Show how the recipient can recover the original message
$(m_0,m_1,m_2)$.
\end{Parts}
\Question{Countability Introduction}
\begin{Parts}
\Part Do $(0, 1)$ and $\R_+ = (0, \infty)$ have the same cardinality? If so, give an explicit bijection (and prove that it's a bijection). If not, then prove that they have different cardinalities.
\Part Is the set of English strings countable? (Note that the strings may be arbitrarily long, but each string has finite length.) If so, then provide a method for enumerating the strings. If not, then use a diagonalization argument to show that the set is uncountable.
\Part Consider the previous part, except now the strings are drawn from a countably infinite alphabet $\mathcal{A}$. Does your answer from before change? Make sure to justify your answer.
\end{Parts}