\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query

\begin{document} 
\inclassproblems{5, Mon.}                    % !! start the paper

\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}

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

{\em Note: For today only, if you \underline{arrived on time} for
class, then you are permitted to condescend to your TA as a rude
customer might treat a waiter.  Please make the most of this unique
privilege!  If you arrived late, however, please be respectful of your
TA at all times.}

\begin{problem}

Usually, 8 bits are used to represent each symbol in a text file.
Here are the standard representations for a few symbols:

\[
\begin{array}{ccc}
\text{symbol} & \text{code} & \text{code length} \\
\texttt{e} & 01100101 & 8 \text{ bits}\\
\texttt{T} & 01010100 & 8 \text{ bits} \\
\texttt{|} & 01111100 & 8 \text{ bits}
\end{array}
\]

Alternatively, we could represent {\em common} symbols (such as
\texttt{e} and \texttt{T}) with fewer bits and {\em rare} symbols
(such as \texttt{|}) with more bits.  This would make most text files
smaller, since most text files consist mainly of common characters.
Let's try out this idea with an eight-symbol alphabet and the
following coding scheme:

\[
\begin{array}{ccc}
\text{symbol} & \text{code} & \text{code length} \\
\textsc{[space]} & 00 & 2 \text{ bits} \\
\texttt{t} & 01 & 2 \text{ bits} \\
\texttt{o} & 100 & 3 \text{ bits} \\
\texttt{i} & 101 & 3 \text{ bits} \\
\texttt{n} & 110 & 3 \text{ bits} \\
\texttt{d} & 1110 & 4 \text{ bits} \\
\texttt{w} & 11110 & 5 \text{ bits} \\
\texttt{k} & 11111 & 5 \text{ bits}
\end{array}
\]

\bparts

\ppart Here is an encoded text file.  Can you decipher it?  Verify
that your teammates got the same answer!

\[
10100111010011001001111111010011110 
\]

\solution[\vspace{1in}]{
The message is, ``\texttt{i dont know}''.
}

\ppart Encoding $w$ as 1011 would make text files even more compact.
Can you find a problem with this scheme?

\solution[\vspace{2in}]{If $w$ is encoded as 1011, then one can not
always determine the original message from the encoded file.  For
example:

\begin{eqnarray*}
101100
    & = & \underbrace{101}_{\texttt{i}}\ \underbrace{100}_{\texttt{o}} \\
    & = & \underbrace{1011}_{\texttt{w}}\ \underbrace{00}_{\texttt{[space]}}
\end{eqnarray*}
}

\ppart A coding scheme is {\em prefix-free} if no symbol's code is a
prefix of another symbol's code.  (For example, 101 is a prefix of
10110.)  Messages encoded using a prefix-free code are always
decodable.

Here is a rooted binary tree with some labels.  Can you describe all
prefix-free coding schemes in terms of similar rooted binary trees?

\mfigure{!}{2.5in}{cp5m-bintree}

\solution[\newpage]{In a rooted binary tree, suppose the root is
labeled with the empty string, and a node with label $s$ has children
labeled $s0$ and $s1$.  Then the symbol codes in a prefix-free coding
scheme are (at least a subset of) the leaf labels in such a tree.}

\ppart Can you find a prefix-free coding scheme for an eight-symbol
alphabet with code lengths 2, 2, 3, 3, 3, 4, 4, and 5?

\solution[\vspace{2in}]{No.}

\ppart Define the {\em weight} of a leaf in a rooted binary tree to be
$2^{-l}$, where $l$ is the distance from the leaf to the root.

\begin{theorem*}
The total weight of all leaves in a rooted binary tree is 1.
\end{theorem*}

How does this relate to the previous question?  Prove the theorem by
strong induction on the height of the tree.  (The {\em height} of a
rooted tree is the length of the longest root-to-leaf path.)

\solution{The previous question asks, in effect, whether there exists
a rooted binary tree which has root-to-leaf distances 2, 2, 3, 3, 3,
4, 4, and 5.  The total weight of these leaves would be:

\begin{eqnarray*}
\frac{1}{2^2} + \frac{1}{2^2} + 
\frac{1}{2^3} + \frac{1}{2^3} + \frac{1}{2^3} + 
\frac{1}{2^4} + \frac{1}{2^4} +
\frac{1}{2^5}
    & = & \frac{33}{32} \\
    & > & 1
\end{eqnarray*}

The theorem implies that no such tree exists.  Therefore, no
corresponding prefix-free coding scheme exists.

\begin{proof}
We use strong induction on the height of the tree.  The induction
hypothesis is that the total weight of all leaves in a rooted binary
tree is 1.  For a tree of height 0, the only leaf is the root, which
has weight 1.  So the claim holds in this case.

Now suppose that the total weight of all leaves in a rooted binary
tree of height $n$ is 1.  Consider a rooted binary tree of height $n +
1$.  Removing the root vertex creates two subtrees, $L$ and $R$, of
height at most $n$.

\mfigure{!}{1.5in}{cp5m-tree}

By induction, the total weight of all leaves in each subtree is
exactly 1.  Adding back the root vertex increases the distance from
each leaf too the root by 1, which reduces the weight of each leaf by
half.  Therefore, the total weight of all leaves the whole tree is
$\frac{1}{2}(1 + 1) = 1$.  The theorem follows by induction.
\end{proof}
}

\eparts

\end{problem}

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

\end{document}
