\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.
  
\item In $O(n \lg n)$ time, determine $x, y \in S$ such that $|x - y|$
  is minimum.

\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.)
\end{enumerate}

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

{\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 4. (20 points)} Problem~13--2, page 260.
\end{document}
