\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 5} \\ Due
Thursday, March 12, in Recitation
\end{center}
\begin{quote}
I wasn't sure anymore and I will tell you, it is a strange
process to feel one's mind changing, allowing ideas into
your brain which it had once considered unthinkable. I
cannot say it's painful, or particularly pleasurable, but
that it requires a certain relaxation of the hold one keeps
over oneself, and is to that degree both a thrill and a
horror.
\\ -- from The Chess Garden, by Brooks Hansen
\end{quote}
\ben
\item Some exercises in which $n$ is NOT the data size but we want
the answer in terms of $n$. (Answers in $\Theta$-land.)
\ben
\item How long does {\tt MERGE-SORT} on $n^2$ items take?
\item Suppose that when $n=2^m$, {\tt ANNA} takes time $\Theta(m^22^m)$.
How long does it take as a function of $n$.
\item Suppose that when $n=2^m$, {\tt BOB} takes time $\Theta(5^m)$.
How long does it take as a function of $n$.
\item How long does {\tt COUNTING-SORT} take to sort $n^2$ items with
each item in the range $0$ to $n^3-1$.
\item How long does {\tt RADIX-SORT} take to sort $n^2$ items with
each item in the range $0$ to $n^3-1$ and base $n$ is used.
\een
\item
Consider hashing with chaining using as hash function the sum of the numerical
values of the letters (A=1,B=2,...,Z=26) mod 7. For example, h(JOE)=
10+15+5mod7 = 2. Starting with an empty table apply the following
operations. Show the state of the hash table after each one. (In the
case of Search tell what places were examined and in what order.)
\\ Insert COBB
\\ Insert RUTH
\\ Insert ROSE
\\ Search BUZ
\\ Insert DOC
\\ Delete COBB
\item Wally Wonkle, NYU drone, is asked to create a hash table (by chaining)
of the 20000 NYU student records. Each record takes about 10K bytes of memory.
He decides to use a hash table of size one million and The Boss goes ballistic,
accusing him of negligent use of precious computer space. Argue coherently
that this method is not using very much more space than a hash table of
size 20000. What is the advantage in using size one million instead of
size 20000?
\item
Consider a Binary Search Tree $T$ with vertices $a,b,c,d,e,f,g,h$
and $ROOT[T]=a$ and with the following values ($N$ means NIL)
\begin{center}
\begin{tabular}{r|rrrrrrrr}
vertex & a&b&c&d&e&f&g&h \\
parent & N&e&e&a&d&g&c&a \\
left & h & N & N & e & c & N & f & N \\
right & d & N & g & N & b & N & N & N \\
key & 80 & 170 & 140 & 200 & 150 & 143 & 148 & 70
\end{tabular}
\end{center}
Draw a nice picture of the tree.
Illustrate {\tt INSERT[i]} where {\tt key[i]=$100$}.
\een
\begin{quote}
If you want to have good ideas you must have many ideas. Most of
them will be wrong, and what you have to learn is which ones to
throw away.
\\ -- Linus Pauling
\end{quote}
\end{document}