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

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

\head{1390}{Algorithms}{Winter 1999}{2 February 1999}{10}

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

\bigskip
{\bf 1.} (5 + 8 + 12 = 25 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
Let $M$ and $m$ denote the maximum and minimum numbers in $S$, respectively.
In $O(n)$ time, determine $x, y \in S$ such that
\[|x - y| \le \frac{1}{n-1}(M - m).\]
That is, determine any two numbers that are at least as close together as the
average distance between consecutive numbers in the sorted order.

({\em Hint:} Use divide and conquer.)
\end{enumerate}

{\bf 2.} (6 + 8 + 6 = 20 points) While the worst-case running time of both
insertion sort and quicksort is $\Theta(n^2)$, quicksort is considered an
efficient sorting algorithm because the randomized version of quicksort has an
expected running time of $\Theta(n \lg n)$ (as we have seen in class).  In
this exercise, we take a closer look at insertion sort.  (For the pseudocode
of insertion sort, you may refer to your class notes or to Section 1.2 of
text.)

Let $A[1..n]$ be an array of distinct numbers.  If $i < j$ and $A[i] > A[j]$,
then we say that the pair $(i,j)$ is an {\em inversion}\/ of $A$.

\begin{enumerate}
\item[(a)]
When does an array have the minimum number of inversions?  What is this
minimum number?  When does an array have the maximum number of inversions?
What is this maximum number?

\item[(b)] 
If $T(A)$ is the running time of insertion sort on input $A$ and $I(A)$ is the
number of inversions in $A$, then prove that $T(A)$ is $\Theta(I(A) + n)$.

\item[(c)]
Based on part~(b), comment on Exercise~8.2--3 of the textbook.

\item[(d)] (10 bonus points)
Show that if $A$ is a random permutation chosen uniformly at random
from the set of all $n!$ permutations, then the expected number of
inversions is $\Theta(n^2)$.  Using part~(b), derive a tight bound on the
expected running time of insertion sort on a random permutation.
\end{enumerate}

{\bf 3.} (15 points) Exercise~31.2--4.
\end{document}