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

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

\head{1390}{Algorithms}{Winter 2001}{1 February 2001}{10}

\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 Problem Set 3 (due February 8)}
\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 ots
worst-case running time, as you can.

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

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

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

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