\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\ah}{\alpha}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\NIL}{{\tt NIL}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Problem Set 3}
\\ Due Thursday, September 26
\end{center}
\begin{quote}
Well, you see, Haresh Chacha, its like this. First you have ten, that's
just ten, that is, ten to the first power. Then you have a hundred, which
is ten times ten, which makes it ten to the second power. Then you have a
thousand which is ten to the third power. Then you have ten thousand,
which is ten to the fourth power - but this is where the problem begins,
don't you see? We don't have a special word for that, and we really
should. \ldots But you know, said Haresh, I think there is a special
word for ten thousand. The Chinese tanners of Calcutta once told me that
they used the number ten-thousand as a standard unit of counting. What
they call it I can't remember \ldots Bhaskar was electrified. But Haresh
Chacha you must find that number for me, he said. You must find out what
they call it. I have to know, he said, his eyes burning with mystical fire
and his small frog-like features taking on an astonishing radiance.
\\ -- from A Suitable Boy by Vikran Seth
\end{quote}
\ben
\item Write each of the following functions as $\Theta(g(n))$ where
$g(n)$ is one of the standard forms:
$2n^3-11n+98$ ;
$6n + 43n\lg n$;
$63n^2 + 14n\lg^5n$;
$3 + \frac{5}{n}$
\item Illustrate the operation of {\tt RADIX-SORT} on the
list: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG,
TEA, NOW, FOX following the Figure in the Radix-Sort section.
(Use alphabetical order and sort one letter at a time.)
\item Illustrate the operation of {\tt BUCKET-SORT}
(with $10$ buckets)
on the
array \\ $A=(.79,.13,.16,.64,.39,.20,.89,.53,.71,.42)$ \\ following
the Figure in the Bucket-Sort section.
\item Given $A[1\cdots N]$ with $0\leq A[I]