\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Assignment 8}
\\ Due November 14 in Recitation
\end{center}
\begin{quote}
The search for truth is more precious than its possession
\\ -- Albert Einstein
\end{quote}
\ben
\item Suppose that the Huffman Code for $\{v,w,x,y,z\}$ has $0$ or $1$ as the
code word for $z$. {\em Prove} that the frequency for $z$ cannot be less than
$\frac{1}{3}$. {\em Give an example} where the frequency for $z$ is $0.36$ and
$z$ does get code word $0$ or $1$.
\item Suppose, in the Activity Selector problem, we
instead select the last activity to start that is compatible with all previously
selected activities. Describe how this
approach works, write a program for it (psuedocode allowed) and prove that it
yields an optimal algorithm.
\item Students (professors too!) often come up with very clever ideas for
optimization programs. The problem (often!) is that they (sometimes, but that
is enough) give the wrong answer. Here are three approaches and {\em your} problem,
in each case, is to give an example where it yields the wrong answer.
\ben
\item Pick the activity of the shortest duration
from amongst those which do not overlap previously selected activities.
\item Pick the activity which overlaps the fewest other remaining activities
from amongst those which do not overlap previously selected activities.
\item Pick the activity with the earliest start time
from amongst those which do not overlap previously selected activities.
\een
\item
\ben \item What is an optimal Huffman code for the following code when the
frequencies are the first eight Fibonacci number?
\[ a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21 \]
\item
The Fibonacci sequence is defined by initial values $0,1$
with each further term the sum of the previous two terms. Generalize
the previous answer to find the optimal code when there are $n$ letters with
frequencies the first $n$ (excluding the $0$) Fibronacci numbers.
\een
\item Suppose that in implementing the Huffman code we weren't
so clever as to use Min-Heaps. Rather, at each step we found
the two letters of minimal frequency and replaced them by
a new letter with frequency their sum. How long would that
algorithm take, in Thetaland, as a function of the initial number of
letters $n$.
\een
\begin{quote}
Dear Sir,
\\ I beg to introduce myself to you as a clerk in the Accounts Department
of the Port Trust Office at Madras on a salary of only \pounds 20 per
annum. I am now about 25 years of age. I have no University education but
I have undergone the ordinary school course. After leaving school I have
been employing the spare time at my disposal to work at Mathematics\ldots
I am striking out a new path for myself. I have made a special investigation
of divergent series in general and the results I get are termed
by the local mathematicians as ``startling" \\ -- Ramanujan
\end{quote}
\end{document}