\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}
\newcommand{\k}{\mbox{\it key}}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 1999}{8 February 1999}{12}

\begin{center}
\Large{\bf Sample Solution to Problem Set 3}
\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.

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

{\bf Answer:} For convenience, let $k$ denote $(M - m)/(n - 1)$.  Let us first
see why should there be two numbers $x$ and $y$ such that $|x - y| \le k$.
Consider all of the elements in $S$ in increasing order: $s_1, s_2, \ldots,
s_i, \ldots, s_n$.  Thus, $s_1 = m$ and $s_n = M$.  We now claim that there
exist two consecutive numbers $s_{i-1}$ and $s_i$ in the sorted order whose
difference is at most $k$.  If not, then we can derive the following
contradiction.  By adding up the differences between consecutive pairs of the
numbers, then we should get $M - m$.  But if every difference is greater than
$k$, then since there are $n - 1$ such differences, they will add up to $> k
(n - 1) = M - m$, a contradiction.  \junk{More formally, we can put it in the
following way.  If for all $i$, $s_i - s_{i-1} > k$, then we will obtain:
\[ M - m = \sum_{i = 2}^{n} (s_i - s_{i - 1}) > (n - 1)k = M - m,\]
a contradiction.  Therefore, there exists an $i$ such that $s_{i} - s_{i-1}
\le k$.  }

Of course, our problem is to {\em find}\/ two numbers $s_i$ and $s_{i-1}$ such
that $s_i - s_{i-1} \le k$.  Our approach in solving the problem is the
following.  Suppose we find the median $x$ of the set $S$.  Let $S_1$ be the
set of elements less than or equal to $x$ and $S_2$ be the set of elements
greater than or equal to $x$.  Note that both $S_1$ and $S_2$ contain $x$.
Thus, if $n_1 = |S_1|$ and $n_2 = |S_2|$, then $n_1 + n_2 = n + 1$ elements.
The key idea is the following.  If $(M - x)/(n_1 - 1) \le k$, then we can
search for the desired elements in $S_1$.  If $(x - m)/(n_2 - 1) \le k$, then
we can search for the desired elements in $S_2$.  And, crucially, either $(M -
x)/(n_1 - 1)$ or $(x - m)/(n_2 - 1)$ has to be at most $k$.  Why?  Because if
both are greater than $k$, then we get $M - x > (n_1 - 1)k$ and $x - m > (n_2
- 1)k$, leading to:
\[ M - m = M - x + x - m > (n_1 - 1 + n_2 - 1)k = (n - 1)k = M - m,\]
a contradiction.  So we can now define the following algorithm.

\begin{tabbing}
{\sc Search}$(S)$\\
1. \= Find the minimum $m$ and maximum $M$ of $S$\\
2. \> \myif\ $n = 2$, then \ret\ $m$ and $M$\\
3. \> \myelse \= \\
4. \> \> Find the median $x$ of $S$ using {\sc Select}\\
5.\> \> Find $S_1$, the set of elements in $S$ that are less than or equal to
$x$; let $n_1 = |S_1|$\\
6.\> \> Find $S_2$, the set of numbers in $S$ that are greater than or equal to
$x$; let $n_2 = |S_2|$\\
7.\> \> \myif\ $(x - m)/(n_1 - 1) \le (M - m)/(n - 1)$, then \ret\ {\sc
Search}$(S_1)$\\
8.\> \> \myelse\ \ret\ {\sc Search}$(S_2)$
\end{tabbing}

{\sl Analysis of running time.} Step 1 takes $O(n)$ time.  Step 2 takes $O(1)$
time.  Step 4, the calculation of the median, takes $O(n)$ time.  Steps 5 and
6 each take $O(n)$ time.  The comparison in Step 7 takes $O(1)$ time.  Since
$x$ is the median, the sizes of $S_1$ and $S_2$ are both at most $\lfloor
n/2\rfloor + 1$.  Therefore, the recursive call in steps 7 and 8 are to sets
of size at most $\lfloor n/2 \rfloor + 1$.  We thus have $T(n) \le T(\lfloor
n/2 \rfloor + 1) + O(n)$.  If we approximate it by $T(n) = T(n/2) + O(n)$,
then we can invoke case~3 of the Master method as follows.  We have $a = 1$,
$b = 2$, and $f(n) = O(n)$.  Therefore, $n^{\log_b a} = n^0 = 1$.  We thus
have: $n^{\log_b a } = O(f(n)/n^\eps)$ by selecting $\eps = 1$.  This suggests
case~3.  We need to check though that there exists a $c < 1$ such that
$af(n/b) \le c f(n)$.  Since $a = 1$, $b = 2$, and $f(n) = O(n)$, we can
select $c = 1/2$ and verify case~3.  By invoking case~3, we get $T(n) =
\Theta(f(n)) = O(n)$.

{\sl A more precise analysis of running time.}  For a more formal proof, we
use the substitution method to show that $T(n) \le cn$ for all $n \ge 2$.  For
the base case, we set $n = 2$.  Since $T(2)$ is clearly a constant, we can
always choose $c$ such that $T(2) \le c$.  Now we move on to the induction
step, where $n \ge 3$.  We will assume that $T(i) \le ci$ for all $i < n$.  We
need to prove that $T(n) \le cn$.  To be concrete, let us replace $O(n)$ in
the recurrence relation by $c_1 n$, where $c_1$ is some given constant.  By
the recurrence relation, we have:
\begin{eqnarray*}
T(n) & \le & T(\lfloor \frac{n}{2} \rfloor + 1) + c_1 n\\
& \le & c (\lfloor \frac{n}{2} \rfloor + 1) + c_1 n\\
& \le & c (n/2 + 1) + c_1 n\\
& \le & (c/2 + c_1 + c/n)n\\
& \le & (c/2 + c_1 + c/3)n\\
& \le & (5c/6 + c_1)n\\
& \le & cn,
\end{eqnarray*}
if we select $c$ such that $c \ge 5c/6 + c_1$, which we can do by picking $c
\ge 6c_1$.  Thus $T(n) = O(n)$.
\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{itemize}
\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?

{\bf Answer:} A fully sorted array has $0$ inversions since whenever $i < j$,
$A[i] \le A[j]$.  Therefore, a fully sorted array has the minimum number of
inversions.  

On the other hand, the array that is inverse sorted has the maximum number of
inversions since every pair $(i, j)$ (for $i < j$) is an inversion.  How many
pairs $(i, j)$ such that $i < j$ are there?  For $i = 1$, there are $n - 1$
possible values for $j$.  For $i = 2$, there are $n - 2$ possible values for
$j$.  In general, for $i$, there are $n - i$ possible values for $j$.
Therefore, the totol number of inversions in an inverse sorted array equals:
\[ \sum_{i = 1}^{n} (n - i) = \sum_{k = 0}^{n-1} k = \frac{(k-1)k}{2}.\]

\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)$.

{\bf Answer:} Consider what happens in the $j$th for loop of insertion sort.
(See pseudocode on page 8 of text.)  At the start of this for loop, all of the
elements in $A[1..j-1]$ have been sorted.  In the for loop, we first set $\k$
to $A[j]$ (line 2) and then compare it with elements $A[j-1]$, $A[j-2]$,
\ldots, (the while-loop in lines 5 through 7) until an element smaller than or
equal to $\k$ is found.  Thus the total number of executions of the
while-statement is exactly equal to 1 more than the number of elements that
are in the first $(j - 1)$ positions and are greater than $A[j]$.  But the
elements that are in the first $(j - 1)$ positions and are greater than $A[j]$
exactly correspond to the number of inversions of the form $(\cdot, j)$ in
$A$.  Thus, if we add over all of the for loops, we get that the total number
of while loop executions is $I(A) + (n - 1)$.  Since there are only a constant
number of operations in each while loop, the running time of insertion sort is
$\Theta(I(A) + n)$.

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

{\bf Answer:} The result of part~(b) implies that the running time of
insertion sort is highly dependent on the number of inversions in the array
$A$.  For example, if the array is sorted, then the number of inversions is
$0$.  Therefore, the running time is $\Theta(n)$.  In fact, even if the number
of inversions is $\Theta(n)$, the running time (from part~(b)) is
$\Theta(n)$.  If there are a large number of inversions, say $\Theta(n^2)$
(which is the case when the array is reverse sorted), then insertion sort
takes time $\Theta(n^2)$.

In the bank account application, the comments in the question suggest that the
array is almost sorted.  That is, the number of inversions may be small.  If
it is $O(n)$, then insertion sort is a better algorithm since it will take
$\Theta(n)$ time, while randomized quicksort takes expected time $\Theta(n \lg
n)$.

\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.

{\bf Answer:} Consider a pair $(i, j)$.  If we select a random permutation,
what is the probability that this pair is an inversion?  Since both $A[i] >
A[j]$ and $A[j] > A[i]$ are equally likely, this probability is $1/2$.
Therefore, any pair $(i, j)$ contributes $1$ to the total number of inversions
with probability $1/2$, and $0$ with probability $1/2$.  Therefore, the
expected contribution of each pair is $1/2$.

As we have seen, there are a total of $n(n-1)/2$ possible pairs $(i, j)$.  Since
the expected contribution  of each pair is $1/2$, the expected total number of
inversions $I(A)$ is $n(n-1)/4$.  Therefore, by part~(b), the expected running
time equals $\Theta(n(n-1)/4 + n) = \Theta(n^2)$. 
\end{itemize}

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

{\bf Answer:} Strassen used the idea that if we can multiply two $2 \times 2$
matrices using $7$ multiplications, then we can reduce the problem of
multiplying two $n \times n$ matrices to $7$ multiplications of $n/2 \times
n/2$ matrices plus $O(n^2)$ time for additions.  Similarly, we can multiply
two $n \times n$ matrices by partitioning each matrix into $68^2$ $n/68 \times
n/68$ matrices and then recursing using V.\ Pan's method for multiplying $68
\times 68$ matrices.  (Note that we are ignoring floors and ceilings.)  This
will reduce the problem in the following way.

Two $n \times n$ matrices can be multiplied by $132464$ multiplications of
$n/68 \times n/68$ matrices plus $O(n^2)$ time for additions.  This gives us
the following recurrence:
\[ T(n) = 132464 T(n/68) + O(n^2).\]
Similarly, if we use V.\ Pan's method for multiplying $70 \times 70$ matrices
and $72 \times 72$ matrices , we get the following recurrences, respectively:
\begin{eqnarray*}
T(n) = 143640 T(n/70) + O(n^2)\\
T(n) = 155424 T(n/72) + O(n^2)
\end{eqnarray*}
Each of the three recurrences can be solved by invoking Case~1 of the master
theorem.  We obtain the following solutions: 
\begin{eqnarray*}
T(n) = \Theta(n^{\log_{68} 132464}) \approx \Theta(n^{2.7951285})\\
T(n) = \Theta(n^{\log_{70} 143640}) \approx \Theta(n^{2.7951227})\\
T(n) = \Theta(n^{\log_{72} 155424}) \approx \Theta(n^{2.7951474})
\end{eqnarray*}
Since Strassen's algorithm takes $T(n) = \Theta(n^{\lg 7}) \approx
\Theta(n^{2.807})$ time, each of V.\ Pan's algorithms is asymptotically better
than Strassen's.  The best V.\ Pan algorithm is the one that uses $70 \times
70$ matrices.
\end{document}