\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 6
\\ Due March 28 in Recitation}
\end{center}
\begin{quote}
I am slow to learn and slow to forget that which I have learned. My
mind is like a piece of steel; very hard to scratch anything on it
and almost impossible after you get it there to rub it out.
\\ -- Abraham Lincoln
\end{quote}
\vspace{1cm}
\ben
\item (Continuation of Problem from Last Assignment))
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
\end{tabular}
\end{center}
\ben
\item Which is the successor of $c$. Illustrate how the
program {\tt SUCCESSOR} will find it.
\item Which is the minimal element? Illustrate how the
program {\tt MIN} will find it.
\item Illustrate the program {\tt DELETE[e]}
\een
\item Draw binary search trees of height 2,3,4,5,6 on the
set of keys \{1,4,5,10,16,17,21\}.
\item What is the difference between the binary-search
property and the heap property? (*) Can the heap property
be used to print out the keys of an $n$-node tree in sorted
order in $O(n)$ time? Explain how or why not.
\item You are given an array $A[1\cdots n]$, whose values
come from a universe $\Omega$. (In application, the values
would be the keys of records.) You want to test if there are any
duplicates, if there are any $1\leq i < j \leq n$ such that
$A[i]=A[j]$. You are given a hash function $h:\Omega\ra \{1,\ldots,n\}$
and a table $T[1\cdots n]$ of linked lists, initially all empty.
Using the hash function, give an algorithm that returns {\tt BAD}
if there is a duplicate and {\tt GOOD} if there is no duplicate.
Discuss the time of the algorithm under the assumption that
calculating the hast function takes unit time.
\item What would the BST tree look like if you start
with the root $a_1$ with $key[a_1]=1$ (and nothing else)
and then you apply \[ INSERT[a_2],\ldots,INSERT[a_n] \] in
that order where $key[a_i]=i$ for each $2\leq i\leq n$?
Suppose the same assumptions of starting with $a_1$ and
the key values but the INSERT commands were done in
{\em reverse} order \[ INSERT[a_n],\ldots,INSERT[a_2] \]
\een
\begin{quote}
He is a down-to-earth mathematician. There are no stuffy definitions and
high theories in his language, just pictures scratched here and there, and
some stray Greek letters as mnemonics. He cannot think sitting in a room.
If you ask him a question, he will repeat the question, check that he
understood the question correctly. He will apologise for being slow; he
will say that he cannot understand anything these days, but that he ``did
understand' the question you posed. Then, he will disappear for a long
walk, in the snow and rain outside. When you meet him next, if he has the
answer, he will start scratching on the board apologising again and again
for his bad handwriting. He will make a claim, and then you must tell him
why the claim might be false (that is, what you think the counter example
might look like); then he will say, oh! that cannot happen because of
this.... Then, you will find another reason why it might be false, and he
will tell you why that can't happen either, and this will go on. At some
point, you give up. He will then say that everything needs to be checked.
He is a careful mathematician.
\\ -- Jaikumar Radhakrisnan, on Endre Szemer\'edi, 2012 Abel Prize Laureate
\end{quote}
\end{document}