\documentclass[11pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{fullpage}

\setlength{\textwidth}{6.5in} \setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in} \setlength{\headsep}{0.0in}
%\setlength{\topsep}{0in}
\setlength{\textheight}{9in} \setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}


%\documentstyle[11pt]{article}
%\usepackage{fullpage}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\pagestyle{empty} \setlength{\textwidth}{6.5in}
%\setlength{\evensidemargin}{0.0in}
%\setlength{\oddsidemargin}{0.0in} \setlength{\topmargin}{-0.25in}
%\setlength{\textheight}{9.0in}
%\setlength{\baselineskip}{1.3\baselineskip}
%\setlength{\parindent}{0in}
%
%\newcommand\qed{\hspace*{\fill} {\large$\Box$}}
%\newcommand\set[1]{\left\{#1\right\}}
%\newcommand\ang[1]{\left\langle #1 \right\rangle}
%\newcommand\brac[1]{{\left[ {#1} \right]}}
%\newcommand\card[1]{\left| #1 \right|}
%\newcommand\inR{{~\in_{\rm R}~}}


\begin{document}



\title{Data Structures - Assignment no. 9, June 27, 2007}

\date{}

\maketitle


\def\lim{\mathop{\rm lim}\nolimits }
\def\true{ {\small\bf TRUE } }
\def\false{ {\small\bf FALSE } }

\vspace{-1.5cm}

 {\small {\bf Remarks:
\begin{itemize}
 \item Write both your name and your ID number very clearly on the
top of the exercise. Write your exercises in pen, or in clearly
visible pencil. Please write \emph{very} clearly.

\item Recall that 80\% of the theoretical exercises must be
submitted. The exercises can and must be worked on and submitted
alone.
\end{itemize} }}



\begin{enumerate}



\item Build a Huffman tree $T$ for a string $s_1$ which contains two `A's,
three `B's, eight `C's, ten `D's, and twelve `E's. Then compress the
string $s_2=$``ABDE'' using the encoding represented by $T$. What is
the size, in bits, of this encoding of $s_2$. What is the size, in
bits, of the encoding of $s_1$?

\item Draw a suffix tree for the string ``mississippi''. Then show
the search path for the sub-string ``ssi'' and for the sub-string
``ssip''.

 \item Let $s$ be a string of length $10^6$, which
consists of $0.99 \cdot 10^6$ `A's and $0.01 \cdot 10^6$ `B's.

\begin{enumerate}

\item Build a Huffman tree for this string.

\item Calculate the length, in bits, of the Huffman encoding of the
string.

\item Can you come up with a better method of encoding the string by
a sequence of bits?\\ \underline{Hint:} $\log_2(10^6) \approx 20$.

\item (Optional. This will not be checked, but we encourage you to think about
it anyway) Why didn't Huffman encoding give good results here? What
drawback of Huffman encoding can you point out? Can you think of a
way to avoid this problem?

\end{enumerate}

\item (Kraft's Inequality)

\begin{enumerate}

\item Let $T$ be a binary tree. For a leaf $v$ of $T$, let
$depth(v)$ be the depth of $v$, measured in edges. Prove that for
any such tree $T$, $\sum_v 2^{-depth(v)} \le 1$, where the sum is
taken over all leaves $v$. (Hint: Use induction on the number of
nodes in the tree).

\item Suppose we work over alphabet $\Sigma =
\{\sigma_1,\ldots,\sigma_k\}$. Let $PF$ be a prefix-free code that
encodes $\sigma_i$ into $\ell_i$ bits. Prove that for any such
prefix-free code $PF$, $\sum_{i=1}^k 2^{-\ell_i} \le 1$. (Hint:
this is a direct consequence of $(a)$).

\item Suppose we work over alphabet $\Sigma =
\{\sigma_1,\ldots,\sigma_k\}$. Let $\ell_1,\ldots,\ell_k$ be
positive integers such that $\sum_{i=1}^k 2^{-\ell_i} \le 1$.
Prove that there exists a prefix-free code $PF$ that encodes
$\sigma_i$ into $\ell_i$ bits.\\
Hint: First, note that you can assume without loss of generality
that $\sum_{i=1}^k 2^{-\ell_i} = 1$. Now, prove the claim by
induction on $k$. You would probably want to use the fact that if
$\ell_i$ is the maximal element among $\ell_1,\ldots,\ell_k$, then
it is easy to see that there is $j \neq i$ such that
$\ell_j=\ell_i$. This follows from the fact that the binary
encoding of $2^{-\ell_i}$ has `1' in its $\ell_i$-th bit, and in
order for $\sum_{i=1}^k 2^{-\ell_i} = 1$ to hold, there must be
another $\ell_j$ with `1' in its $\ell_i$-th bit.

\end{enumerate}


%\item Let $s$ be a string of length $n$ and let $T$ be its suffix
%tree.
%
%\begin{enumerate}
%
%\item What is the maximum possible height of $T$ as a function of
%$n$? (give the answer up to a constant). Give an example, you
%don't have to prove that it is optimal.
%
%\item What is the minimum possible height of $T$ as a function of
%$n$? (give the answer up to a constant). Give an example, you
%don't have to prove that it is optimal.
%
%\end{enumerate}




\end{enumerate}

\end{document}
