% THIS IS NOT THE ORIGINAL LATEX SOURCE.  I ACCIDENTALLY
% DELETED IT.  THIS IS AN OLDER BACKUP.

\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/W00/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 2000}{3 February 2000}{8}

\begin{center}
  \Large{\bf Problem Set 3 (due February 10) -- no late homework}
\end{center}

\bigskip

{\bf 1. (3 + 7 + 10 = 20 points)} Consider a set $S$ of $n$ distinct
numbers given in unsorted order.  Each of the following three problem
parts asks you to give an algorithm to determine two distinct numbers
$x$ and $y$ that satisfy a stated condition.  For each part, describe
your algorithm and then briefly justify the correctness and the
running time of the algorithm.
\begin{enumerate}
\item In $O(n)$ time, determine $x, y \in S$ such that $|x - y|$ is
  maximum.

{\bf Answer:} The two numbers that are farthest apart are the maximum and the
minimum numbers in $S$.  Therefore, find the maximum $M$ and the minimum $m$
of $S$.  This takes $O(n)$ time.  Return $M$ and $m$.
  
\item In $O(n \lg n)$ time, determine $x, y \in S$ such that $|x - y|$
  is minimum.

{\bf Answer:} The two numbers $x$ and $y$ such that $|x - y|$ is minimum must
be consecutive numbers in the sorted order (otherwise, we can replace $x$ by a
number $z$ that lies between $x$ and $y$ and thus obtain $|z - y| < |x - y|$,
leading to a contradiction).  So, we first sort the $n$ numbers.  This takes
$O(n \lg n)$ time.  Then, we scan through the sorted list, keeping track of
the minimum difference between consecutive numbers, and return the two
consecutive numbers that are closest.  This scan takes $O(n)$ time.
Therefore, total running time is $O(n \lg n)$.

\item Given a number $k$, determine in $O(n)$ expected time whether
  there exist $x, y \in S$ such that $x - y = k$.  ({\em Hint:} Use
  hashing.)
  
  {\bf Answer:} We use uniform hashing with chaining.  The size of the
  hash table is $n$.  We now insert the $n$ numbers into the hash
  table.  Since the load factor is $n/n = 1$, the expected cost of an
  insert operation is $\Theta(1)$.  Therefore, the total cost of the
  insert operation is $\Theta(n)$.
  
  Now we go through each of the $n$ numbers and search for a number
  which is $k$ more than the given number.  For example, if we are
  currently considering number $a$, we search for $a + k$ in the hash
  table.  If it exists, then we return the two numbers $a$ and $a +
  k$; otherwise, we proceed.  Each search also takes expected
  $\Theta(1)$ time.  Since there are $n$ searches, the total running
  time is expected $\Theta(n)$.

\end{enumerate}

{\bf 2. (20 points)} Exercise~12.4--1, page~240.

{\bf Answer:} The three hashing techniques yield the following results:

\begin{itemize}
\item {\bf Linear probing:} The key $10$ goes into location $10$, $22$
  into $0$, $31$ into $9$, $4$ into $4$, $15$ after colliding with $4$
  goes into location $5$, and so on.  The final result is:

\[ [22 , 88 ,  , 4 , 15 , 28 , 17 , 59 , 31 , 10 , ].\]

\item {\bf Quadratic probing:} 

\[ [22 , ,  , 4 , 88 , 59 , 28 , 15 , 31 , 10 , 17].\]

\item {\bf Double hashing:}

\[ [22 , 59 , 17 , 4 , 15 , 28 , 88 , , 31 , 10 , ].\]
\end{itemize}

{\bf 3. (20 points)} Is the operation of insertion in binary search
trees ``commutative'' in the sense that inserting $x$ and then $y$
into a binary search tree leaves the same tree as inserting $y$ and
then $x$.  Argue why it is or give a counterexample.  Similarly,
determine whether the operation of deletion is commutative.

{\bf Answer:} The operation of insertion is not commutative.  Consider
inserting $x$ then $y$.  We get $x$ as the root, and $y$ as its child.
Now consider inserting $y$ then inserting $x$.  We get $y$ as the root
and $x$ as its child.

The operation of delete is also not commutative. 

{\bf 4. (20 points)} Problem~13--2, page 260.

{\bf Answer:} We use a radix tree to maintain the strings in $S$.  For
this, we define two operations: {\sc insert} and {\sc tree-walk}.
Both of these are analogous to the operations defined for binary search trees. 

For inserting string $a = a_0a_1\ldots a_p$, we traverse the radix
tree using the bits of $a$ in the order $a_0$, $a_1, \ldots, $a_p$.
As in the search procedure, we go left at a node of depth $i$ if $a_i
= 0$ and right if $a_i = 1$.  If we reach a {\sc Nil} node, then we
create a new node and continue.  Finally, we store the string $a$ at a
leaf node or at an unoccupied node, when we have considered the bit
$a_p$.  The insertion of a string takes time proportional to its
length.  Thus, the total time taken for inserting all the strings is
$\Theta(n)$.  We also note that the total number of edges in the radix
tree after all of the strings have been inserted exactly equals $n$.

For the {\sc tree-walk} procedure, we proceed exactly as the procedure
{\sc Inorder-Tree-Walk}, the only difference being that we only print
those nodes which are occupied by the strings.  This traversal also
takes $\Theta(n)$ time since the number of edges in the tree is
$\Theta(n)$.
\end{document}
