\documentstyle[11pt]{article}

\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}

\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcounter{questnum}
\newcommand{\question}[1]{
\vspace{.1in}
  \refstepcounter{questnum}
{\bf \medskip Problem \thequestnum: }}

\newcommand{\titledquestion}[2]{
 \refstepcounter{questnum}
{\bf \medskip Problem \thequestnum:} #2 {\normalsize (#1 pts) \\}}

\newcommand{\answerspace}{\verb+                                  +
\underline{\makebox[2.0in]{}}}
\newcommand{\smanswerspace}{\underline{\makebox[0.5in]{}}}

\setlength{\topmargin}{-0.5 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{8.75 in}
\setlength{\textwidth}{6.5 in}
\setlength{\parindent}{0.0 in}

\begin{document}

{\large 
CS294-3: Algorithms in the real world \hfill Assignment 1 (Compression)\\[.03in]
Due: Friday Sept 12, 1997\\[.1in]
}

{\bf Collaboration policy:} You are welcome to talk about this or
other assignments with others and even discuss problems using a
whiteboard or scratch paper.  You are not allowed, however, to show or
give any work that you did on your own pertaining to the assignment to
someone else.

\question{??}
Assume an alphabet $S = \{a,b,c\}$ has the probabilities

\[
\begin{array}{ccc}
  p_a = .2 & p_b = .7 & p_c = .1
\end{array}
\]

\begin{description}
\item[(a)] What is the entropy $H(S)$?

\item[(b)] What is the average length of the Huffman code for $S$ (remember
to weigh
the average based on the probabilities).

\item[(c)]
What is the average length of the Huffman code if you group
characters into pairs.

\item[(d)]
For a long string what is the average per-character length of 
an arithmetic code for $S$ (assume the asymptotic value and
that the message abides by the probabilities).

\item[(d)]
For a long string what is the average per-character length of an
arithmetic code for $S$ assuming your model are the probabilities
given above, but you are coding a message which consists of just $c$'s
(i.e., your data does not fit your model).

\item[(e)]
Given the following conditional probabilities what is the 
conditional entropy (this is the average per-character
length that would be achieved by a good code that takes
advantage of the probabilities).

\[
\begin{array}{ccc}
  p(a|a) = .25 & p(a|b) = .65 & p(a|c) = .1 \\
  p(b|a) = .1 & p(b|b) = .8 & p(b|c) = .1 \\
  p(c|a) = .8 & p(c|b) = .1 & p(c|c) = .1 \\
\end{array}
\]

The notation $p(x|y)$ is the probability of $x$ given that
the previous character is $y$.
\end{description}

\question{??}
Prove that the average length $l_a = \sum p_i l_i$ for a Huffman code 
for a set of messages $S$
is bounded by the inequality $l_a \leq H(S) + 1$.
Note that given a maximum probability $p_m$ a tigher upper bound
of
\[
l_a <
\begin{array}{ll}
H(S) + p_m & p_m < .5 \\
H(S) + p_m +.086 & p_m \geq .5
\end{array}
\]
can be shown.
Feel free to prove this stronger result.

\question{??}
Assume we are coding a 4 letter alphabet with LZW and we start
with the dictionary containing the 4 letters $\{a,b,c,d\}$ in
locations 0, 1, 2 and 3.  Entries are added to the dictionary
in sequential order.
Decode the following message that was coded with LZW.

\begin{verbatim}
      0 0 1 2 4 7
\end{verbatim}

\question{??}
Using the LZSS (the variant of LZ77 described in the reading
``Introduction to data compression'' by Peter Gutmann) and assuming a
window size $W$ and a lookahead buffer size $B$, how many code words
will it take to code a message of length $L$ that contains all the same
character.  Assume each <offset,size> pair or character is a codeword.
Also assume the window is initialized to some other character.

\question{??}
Lets say we had the following sequence of values

\begin{verbatim}
   10 11 12 11 12 13 12 11 10 -10 8 -7 8 -8 7 -7
\end{verbatim}

\begin{description}
\item[(a)]
Would we would get better compression by doing a cosine
transform across the whole group of 16 or by blocking the 16 entries
into two groups of 8 and transforming each separately?  Explain
briefly?

\item[(b)]
If using a wavelet transform are we better off blocking
the entries into two groups of 2?
\end{description}

\end{document}

Extra problems not to be handed in but that you might try.

Given the frequency counts
 a = 37, b =38, c=55
what is word length required

Assuming you use this word length, encode aacba

\question{??}  
Assume that we do not use scalar quantization in JPEG to quantize the
elements of the transformed 8x8 blocks.  Why might we get 
better compression compared to coding the untransformed
data.  Assume the number of possible values for both the transformed
and untransformed data are the same.