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

%\showsolutions                 % !! use to force solutions & skip query
\hidesolutions                 % !! use to force no solutions & skip query

\begin{document} 
\inclassproblems{7}

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

\begin{problem}
(Several easy counting problems go here.)
\end{problem}

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

\begin{problem}
On problem set 7, we saw that there is no reversible procedure that
compresses 5-megabyte files down to 1-megabyte files.  Data
compression programs work by exploiting patterns or special properties
of the input file.  For example, let's try to compress $n$-bit files
such that exactly $\alpha n$ of the bits are 1's, where $0 < \alpha <
1$ and $\alpha n$ is an integer.  Such files might represent
black-and-white images where $\alpha$ is the fraction of white pixels.

\bparts

\ppart How many different $n$-bit files with exactly $\alpha n$ 1's
are there?

\solution{
\[
\binom{n}{\alpha n}
\]

We must choose $\alpha n$ of the $n$ bits to make 1's and the
remaining bits are 0's.
}

\ppart Give an approximation to your answer of the form:

\[
2^{n H(\alpha)}
\]

where $H$ is a nasty-looking function involving logarithms.  Use the
following crude version of Stirling's formula:

\begin{eqnarray*}
n! & \approx & \left( \frac{n}{e} \right)^n
\end{eqnarray*}

($H$ is called the {\em entropy function} and plays a central role in
the field of Information Theory.)

\solution{
\begin{eqnarray*}
\binom{n}{\alpha n}
	& = &	\frac{n!}{(\alpha n)! \ ((1 - \alpha) n)!} \\
	& \approx & \frac{\left( \frac{n}{e} \right)^n}
		{\left( \frac{\alpha n}{e} \right)^{\alpha n} \cdot
		 \left( \frac{(1 - \alpha) n}{e} \right)^{(1 - \alpha)n}} \\
	& = &	\left(\frac{1}{\alpha^{\alpha} \cdot (1 - \alpha)^{1 - \alpha}}
		\right)^n \\
	& = &	2^{n \cdot \left(\alpha \log\left(\frac{1}{\alpha}\right)
		+ (1-\alpha) \log\left(\frac{1}{1-\alpha}\right)\right)}
\end{eqnarray*}

The first step uses the definition of the binomial notation.  The
second step uses Stirling's formula.  In the third step, we cancel
lots of $n$'s and $e$'s.  The final step uses the rule $u = 2^{\log
u}$.  (All logarithms here are base 2.)
}

\ppart Describe a reversible procedure that compresses each $n$-bit
file with exactly $\alpha n$ 1's down to an (approximately) $n
H(\alpha)$-bit file.  Your procedure can be incredibly inefficient; it
just has to work!

\solution{Index all the possible files $0, 1, 2, \ldots, \approx 2^{n
H(\alpha)}$ in any way.  The compressed form of a file is its index.
Each index is a number representable with $n H(\alpha)$ bits.}

(Intuitively, a random bit that is 1 with probability $\alpha$
contains $H(\alpha)$ bits of information.  On this intuitive basis, an
$n$-bit file with $\alpha n$ randomly-distributed 1's should contain
about $n H(\alpha)$ bits of information and therefore should be
representable with an $n H(\alpha)$-bit file.)

\ppart (Requires a calculator.)  Suppose that you have a 5-megabyte
file and 90\% of the bits are 1's.  Using the procedure you described
above, how large is the compressed file?

\eparts

\end{problem}

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

\begin{problem}
An {\em $n$-bit boolean function} maps each $n$-bit string to a single
bit; that is, a $n$-bit boolean function has the form $f : \set{0,1}^n
\to \set{0,1}$.

\bparts

\ppart How many $n$-bit boolean functions are there?

\solution{We can map each of the $2^n$ elements of the domain to
either 0 or 1.  Therefore, the number of such functions is:
\[
2^{2^n}.
\]
}

\ppart The $n$-bit boolean function $f$ {\em depends on bit $i$}
if there exist $n$-bit strings $b$ and $b'$ such that $b$ and $b'$
differ only in the $i$-th bit and $f(b) \neq f(b')$.  How many $n$-bit
boolean functions are there that do {\em not} depend on the $i$-th bit?

\solution{Now we can map each of the $2^{n-1}$ domain elements with a
0 in the $i$-th position to either 0 or 1.  Each of the domain
elements with a 1 in the $i$-th position must be mapped to the same
value as the corresponding element with a 0 in the $i$-th position.
Therefore, the number of boolean functions that do not depend on the
$i$-th bit is:
\[
2^{2^{n-1}}.
\]
}

\ppart How many $n$-bit boolean functions depend on {\em every}
bit?  Use inclusion-exclusion.  Your answer should be a summation.

\solution{Generalizing the argument above, the number of $n$-bit
boolean functions that do not depend on a $k$ specified bits is
$2^{2^{n-k}}$.  By the inclusion-exclusion formula, the number of
functions that depend on every bit is the total number of functions,
minus the number that depend on one bit, plus the number the depend on
two bits, minus the number that depend on three bits, etc.  This
gives:
\[
\sum_{k=0}^{n} (-1)^k \cdot \binom{n}{k} \cdot 2^{2^{n-k}}
\]
}

\eparts

\end{problem}

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

\begin{problem}
Recall the recursive definition for the set $W$ of {\em well-formed
parenthesis strings}:

\begin{enumerate}

\item The empty string, $\lambda$, is in $W$.

\item If $s$ and $t$ are in $W$, then $(s)t \in W$.

\end{enumerate}

\bparts

\ppart Let $C_i$ be the number of well-formed parenthesis strings with
exactly $i$ pairs of parentheses.  Compute $C_0, \ldots, C_4$.

\ppart Translate the recursive definition of the set $W$ in to a
recurrence equation expressing $C_{n+1}$ in terms of smaller Catalan
numbers.  (Observe that every well-formed parenthesis string with
$n+1$ pairs of parentheses must be formed using rule 2 where $s$ has
$k$ pairs of parentheses and $t$ has $n - k$ pairs for some $0 \leq k
\leq n$.)

\ppart The numbers $C_0, C_1, C_2, \ldots$ are called the {\em Catalan
numbers}.  They arise in many different counting problems.  For
example, Theory Hippo wants to walk from point $A$ to point $B$ on an
$n \times n$ grid without falling into the Flaming Chasm of Hideous
Death:

Each step carries Theory Hippo either 1 unit north or 1 unit east.
Show that Theory Hippo has $C_n$ routes available by describing a
bijection between well-formed parenthesis strings and safe paths
across the grid.

\ppart Some examples of {\em rooted ordered binary trees} are shown
below.

\bigskip
\centerline{figure goes here}
\bigskip

Determine the number of rooted ordered binary trees with $n$ vertices
by describing a bijection with well-formed parenthesis strings.  (As a
first step, you might try to associate each of the example trees above
with a specific parenthesis string.)

\ppart A {\em triangulation} of a convex polygon is a way of cutting
the polygon into triangles.  Some polygon triangulations are shown
below.

\bigskip
\centerline{figure goes here}
\bigskip

Show that a convex $(n+2)$-gon can be triangulated in $C_n$ different
way by describing a bijection with well-formed parenthesis strings.

\eparts

\end{problem}

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

\end{document}
