\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{courseMacros}

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

\head{1390}{Algorithms}{Winter 2001}{13 February 2001}{14}

\newcommand{\hanoi}{\mbox{{\sc Hanoi}}}
\newcommand{\spare}{\mbox{{\em spare}}}
\newcommand{\start}{\mbox{{\em start}}}
\newcommand{\dest}{\mbox{{\em destination}}}
\newcommand{\stooge}{\mbox{\sc Stooge-Sort}}
\newcommand{\bs}{\mbox{\sc BubbleSort}}
\newcommand{\is}{\mbox{InsertionSort}}
\newcommand{\key}{\mbox{{\em key}}}

\begin{center}
\Large{\bf Sample Solution to Problem Set 3}
\end{center}

{\bf 1. Deletion from a heap} 

Design an efficient algorithm that, given a heap $A[1..n]$ and an
index $i$ in $[1,n]$, removes element $A[i]$ from the heap and returns
a new heap $A[1..n-1]$.  Analyze the worst-case running time of your
algorithm.  Make your algorithm as efficient, in terms of its
worst-case running time, as you can.

{\bf Answer:} Let $k = A[i]$ denote the value to be deleted.  We first
set $A[i] \leftarrow A[n]$ and reduce the size of the heap by $1$.
Now, the element $A[i]$ may violate the heap property.  We consider
two cases.  In the first case the new $A[i] > k$.  In this case, we
see that the subtree rooted at $i$ is still a heap.  But $A[i] >
A[p[i]]$ may hold and thus the heap property may be violated.  In this
case, we walk up the tree starting from $i$ and correct any heap
violations -- in the same manner as we do for insertion.  Since the
height of the tree is at most $\lceil \lg n \rceil$, the time taken
for this case is $O(\log n)$.

In the second case, the new $A[i] < k$.  In this case, $A[i] <
A[p[i]]$; so no heap violations occur with respect to the parent.
However, heap violations may occur with respect to the children of
$i$.  So we call {\sc Heapify}$(A, i)$ and make this tree a heap.  We
note that this causes no heap violations with respect to the parent of
$i$.  Since the height of the tree is at most $\lceil \lg n\rceil$ and
{\sc Heapify} takes time at most the height of the tree, the time
taken for this case is also $O(\log n)$.

{\bf 2. Average-case analysis of insertion sort}

Insertion sort is a simple iterative sorting algorithm, the pseudocode
for which is given below.
\begin{tabbing}
$\is(A)$\\
1. \= \algfor\ \= $j \leftarrow 2$ to $n$\\
2. \> \> \key\ = $A[j]$\\
3. \> \> $i \leftarrow j - 1$\\
4. \> \> \algwhile\ \= $i > 0$ and $A[i] > \key$\\
5. \> \> \> $A[i+1] \leftarrow A[i]$\\
6. \> \> \> $i \leftarrow i - 1$\\
7. \> \> $A[i+1] \leftarrow \key$
\end{tabbing}
\begin{itemize}
\item[{\bf (a)}] Prove that the worst-case running time for insertion
sort is $\Theta(n^2)$.

{\bf Answer:} The inner while loop executes at most $\ell - 1$ times
when $j = \ell$.  Since the outer for loop increases $j$ from $2$ to
$n$, this implies that the total number of executions of the inner
while loop overall is at most $1 + 2 + 3 + \ldots + n - 1 = n(n-1)/2$.
Furthermore, if the input instance is a reverse sorted array, then the
number of while loop iterations will be $1 + 2 + 3 + \ldots + n - 1 =
n(n-1)/2$.  Thus, the worst-case running time is $\Theta(n^2)$.
\end{itemize}

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).  We now
consider how insertion sort performs on average.

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[{\bf (b)}]
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 total 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[{\bf (c)}] 
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.  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 $\key$ 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 $\key$ 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[{\bf (d)}] 
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)$.  Now invoking part~(c), 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~(c), the expected running time equals $\Theta(n(n-1)/4 + n) =
\Theta(n^2)$.
\end{itemize}

{\bf 3. (10 points) \hs 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.  
\begin{itemize}
\item[{\bf (a)}] Prove that a best location for the central post
office is $(x, y)$, where $x$ is the median of $\{x_1, \ldots, x_n\}$
and $y$ is the median of $\{y_1, \ldots, y_n\}$. 

{\bf Answer:} We show that an optimal location for the central post
office is $(x^*, y^*)$, where $x^*$ is a median of $x_1, \ldots, x_n$
and $y^*$ is a median of $y_1, \ldots, y_n$.  Without loss of
generality, we may renumber the $x_i$'s and $y_j$'s in sorted order.
Note that this is for our argument only.  We do not actually sort the
numbers.  Let $m = \lceil n/2 \rceil$.  Then, $x_{m}$ (resp., $y_{m}$
is a median of $x_1, \ldots, x_n$ (resp., $y_1, \ldots, y_n$).  We now
show that
\[
\sum_{i = 1}^{n} |x_i - x_m| \le \sum_{i = 1}^n |x_i - x|,
\]
for any $x$.  We first consider the case when $x < x_m$.  In this
case, we have
\begin{eqnarray*}
\sum_{i = 1}^{n} (|x_i - x_m| - |x_i - x|) & \le & 
\sum_{i = 1}^{m-1} |x_m - x| - \sum_{i=m}^n |x_m - x| \\
& \le & 0.
\end{eqnarray*} 
Similarly, if $x > x_m$, we have
\begin{eqnarray*}
\sum_{i = 1}^{n} (|x_i - x_m| - |x_i - x|) & \le & 
- \sum_{i = 1}^{m} |x_m - x| + \sum_{i=m+1}^n |x_m - x| \\
& \le & 0.
\end{eqnarray*} 
By the same argument, we have
\[
\sum_{i = 1}^{n} |y_i - y_m| \le \sum_{i = 1}^n |y_i - y|,
\]
for any $y$.  This shows that $(x_m, y_m)$ is an optimal location for
the post office. 

\item[{\bf (b)}] Using part~(a), argue that the central post office
location can be found in linear time.

{\bf Answer:} Both the coordinates $x_m$ and $y_m$ can be found using
the linear time selection algorithms.  Therefore, the optimal post
office location can be found in linear time.
\end{itemize}
\end{document}
