\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CSU690}{Algorithms and Data}{Spring 2005}{7 February 2005}{6}

\begin{center}
\Large{\bf Problem Set 3 (due Wednesday, February 16)}
\end{center}

{\bf 1. (5 + 5 = 10 points)} Consider a set $S$ of $n$ distinct
numbers given in unsorted order.  Each of the following 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{itemize}
\item[{\bf (a)}] 
In $O(n)$ time, determine $x, y \in S$ such that $|x - y|$ is maximum.
  
\item[{\bf (b)}]
In $O(n \lg n)$ time, determine $x, y \in S$ such that $|x - y|$ is
  minimum.
\end{itemize}

{\bf 2. (5 + 5 + 2 = 12 points) Stooge sort}

Problem 7--3, pages 161-162.

{\bf 3. (8 points) Generating a random uniform permutation}

Exercise 5.3-4, page 105.

{\bf 4. (5 + 5 = 8 points) The effect of group size on {\sc Select}}

In the algorithm {\sc Select} covered in class and described in
Section~9.3 of the text, the input elements are divided into groups of
5.  Will the algorithm work in linear time if they are divided into
groups of 3? How about groups of 7?  Justify your answers.  

({\em Hint:} Obtain recurrence relations for both approaches, and
solve them.)

{\bf 5. (10 points)  Locating the Central Post Office in Manhattan}

We are given the coordinates $(x_1, y_1), \ldots, (x_n, y_n)$, for
each of $n$ houses in Manhattan.  The distance between any two houses
$(a, b)$ and $(c, d)$ is given by $|a - c| + |b - d|$.  This is
referred to as the {\em Manhattan distance}, since the streets in
Manhattan are organized in a grid.

We would like to determine the location for a central post office in
the city such that the sum of the distances of the $n$ houses from the
central post office is minimized.  Design and analyze an efficient
algorithm for this problem.  The more efficient your algorithm is in
terms of its worst-case running time, the more points you will get.

{\bf 6. (10 bonus points) Selection from two sorted lists}

Design and analyze an efficient algorithm to select the median from a
set of $m+n$ keys given in the form of two sorted lists, one of length
$m$ and the other of length $n$.  For convenience, you may assume that
the $m+n$ keys are all distinct.  ({\em Hint:}\/ A running time of
$O(\log(\min\{m,n\}))$ is achievable.)

\end{document}