\documentclass[11pt]{article}
\usepackage{program}


\title{6.046 Problem Set 3}
\author{Chris Laas: Section G}
\date{February 24, 2000}

\pagestyle{myheadings}
\markright{Chris Laas: Section G \hfil 6.046J/18.410J \hfil 2/24/2000}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}}
\NumberProgramstrue
\def\RETURN{\keyword{return}\ }
\def\MOD{\mbox{mod}\ }
\def\text#1{\mbox{ #1 }}

\begin{document}
\maketitle

\section*{Problem 3-1}

For reference, I include the pseudocode for $|Insertion-Sort|$ here.
\begin{program}
|Insertion-Sort|(A)
\quad\tab \FOR j \gets 2 \rdots |Length|(A)
              |key| \gets A[j]
              i \gets j - 1
              \WHILE i > 0 \text{and} A[i] > |key|
                    A[i+1] \gets A[i]
                    i \gets i - 1
                    \untab%
              A[i+1] \gets |key|
              \untab%
\end{program}

\begin{enumerate}
\item%(a)

The key point to note is that the condition that no memory cell has
floated more than k positions away from its original location,
combined with the fact that the array was initially sorted, implies
that any two cells $2k$ or more cells apart maintain their initial
ordering.  In other words, for any $1 \leq x < y \leq n$ such that $y
- x \geq 2k$, $A[y] \geq A[x]$ (assuming the array was initially
sorted in nondecreasing order).  In addition, the execution of
$|Insertion-Sort|$ will never invalidate this condition, since an
element will never be moved {\em away} from its ``correct'' position,
and thus this ``maximal unordered separation'' is nonincreasing.

Thus, if $j > 2k$, then $A[j-2k] \leq A[j]$, and so the inner loop
will terminate after, at most, $2k$ iterations, since the condition
$A[i] \leq |key|$ will be reached after at most $2k$ iterations.  If
$j \leq 2k$, then clearly the inner loop will terminate after, again,
at most $2k$ iterations, since the condition $i = 0$ will be reached
after $j$ iterations.  Thus, for any given $j$, the inner loop will
execute {\bf at most} $2k$ iterations before terminating.

Since the outer loop's body is executed exactly $n-1$ times, and each
iteration takes at most $2k + c = O(k)$ steps, the whole algorithm
runs in at most $O(kn)$ steps.

\item%(b)

The time for $|Insertion-Sort|$ to run on an array where the maximum
float is $i$ is $O(in)$, as shown in part (a); and it is given to us
that the probability that the maximum float is $i$, for
$1 \leq i \leq n-1$, is $2^{-i}$.  Also, the time for
$|Insertion-Sort|$ to run on a sorted array is $O(n)$, and the
probability of this occurring is $2^{-(n-1)}$.  Thus, the average
running time of $|Insertion-Sort|$ is given by

$$ \sum_{i=1}^{n-1} O(in) 2^{-i} + O(n) 2^{-(n-1)} $$

Now, clearly, the second term, $O(n) 2^{-(n-1)}$, is $O(n)$, since
$2^{-(n-1)}$ is a decreasing function of $n$.  It remains to be shown
that the first term is $O(n)$.

We begin with the observation that
$$ \sum_{i=1}^{n-1} O(in) 2^{-i} = O(\sum_{i=1}^{n-1} i n 2^{-i})
                                 = O(n \sum_{i=1}^{n-1} i 2^{-i}) $$
Now, since the closed-form solution of the summation is
$$ \sum_{i=1}^{n-1} i 2^{-i} = 2\left(1 - \frac{n+1}{2^n}\right) $$
and $\frac{n+1}{2^n}$ is strictly positive, we clearly have
$$ \sum_{i=1}^{n-1} i 2^{-i} = O(1) $$

Hence, it's clear that $ O(n \sum_{i=1}^{n-1} i 2^{-i}) = O(n) $
and thus
$$ \sum_{i=1}^{n-1} O(in) 2^{-i} = O(n) $$

Therefore, the average running time of $|Insertion-Sort|$ is
$O(n) + O(n) = O(n)$, i.e. the runtime of insertion sort on this
probability distribution of arrays is linear in the length of the
array.

\end{enumerate}

\newpage


\section*{Problem 3-2}
\begin{enumerate}

\item%(a)

$|Heapify-|A_{min}$ is virtually the same as vanilla $|Heapify|$; the
only difference is some minor bookkeeping to preserve the ``other''
pointers, which it performs while swapping nodes.
\begin{program}
|Heapify-|A_{min}(H, i)
\quad\tab (A_{min}, A_{max}) \gets H
          l \gets |Left|(i)
          r \gets |Right|(i)
          \IF l \leq |Heap-Size|(A_{min}) \text{and} A_{min}[l].|value| < A_{min}[i].|value|
             \THEN |smallest| \gets l
             \ELSE |smallest| \gets i
                   \untab%
             \untab%
          \IF r \leq |Heap-Size|(A_{min}) \text{and} A_{min}[r].|value| < A_{min}[|smallest|].|value|
             \THEN |smallest| \gets r
                   \untab%
             \untab%
          \IF |smallest| \neq i
             \THEN \mbox{exchange\ } A_{min}[i].|value| \leftrightarrow A_{min}[|smallest|].|value|
                   \mbox{exchange\ } A_{min}[i].|other| \leftrightarrow A_{min}[|smallest|].|other|
                   A_{max}[A_{min}[i].|other|].other \gets i
                   A_{max}[A_{min}[|smallest|].|other|].other \gets |smallest|
                   |Heapify-|A_{min}(H, |smallest|)
                   \untab%
             \untab%
\end{program}

\newpage
\item%(b)

Again, the outline of the algorithm is the same as the simple version;
the difference is that two Heapifies are performed to maintain the
heap property on both heaps, while retaining the linkages between the
two heaps.
\begin{program}
|Max-Min-Heap-Extract-Max|(H)
\quad\tab (A_{min}, A_{max}) \gets H
          \IF |Heap-Size|(A_{max}) < 1
             \THEN \text{error: heap underflow}
                   \untab%
             \untab%
          |max| \gets A_{max}[1].|value|
          k \gets A_{max}[1].|other|
          A_{max}[1].|value| \gets A_{max}[|Heap-Size|(A_{max})].|value|
          A_{max}[1].|other| \gets A_{max}[|Heap-Size|(A_{max})].|other|
          A_{min}[A_{max}[1].|other|].|other| \gets 1
          |Heap-Size|(A_{max}) \gets |Heap-Size|(A_{max}) - 1
          |Heapify-|A_{max}(H, 1)
          A_{min}[k].|value| \gets A_{min}[|Heap-Size|(A_{min})].|value|
          A_{min}[k].|other| \gets A_{min}[|Heap-Size|(A_{min})].|other|
          A_{max}[A_{min}[k].|other|].|other| \gets k
          |Heap-Size|(A_{min}) \gets |Heap-Size|(A_{min}) - 1
          |Heapify-|A_{min}(H, k)
          \RETURN |max|
\end{program}

\end{enumerate}
\newpage


\section*{Problem 3-3}

(This problem is very similar to problem 1, part a, at least on the
insertion-sort side of things.)

I assume, for simplicity, that we're sorting in nondecreasing order.

The modified $|Quick-Sort|$ runs in $O(n \lg (n/k))$ expected time.
The most intuitive and simplistic argument for this is that, by not
recursing over partitions of size less than $k$, the algorithm cuts
off the bottom $\Theta(\lg k)$ layers of the recursion tree; hence,
the expected height of the recursion tree is
$\lg n - \lg k = \lg (n/k)$, and hence the expected runtime is
$O(n \lg (n/k))$.

A more detailed, but similar, model points out that, by not recursing
over partitions of size less than $k$, the algorithm cuts out
$\Theta(k \lg k)$ time for each of $\Theta(n/k)$ ``final'' partitions;
hence, the expected run time of the modified quicksort algorithm is
$O(n \lg n - \frac{n}{k} k \lg k) = O(n \lg n - n \lg k)
 = O(n (\lg n - \lg k)) = O(n \lg (n/k))$.

The rigorous mathematical proof of the $O(n \lg (n/k))$ runtime
depends on the fact that the recursion formula for the quicksort
runtime has not changed; rather, only the base case has changed from
$T(1) = \Theta(1)$ to $T(i) = \Theta(1)$, for all $i < k$.  The
details of the proof are mostly unchanged, and so I'll refrain from
copying it all down here; suffice it to point out that the base case
is satisfied by picking $b$ sufficiently large so that
$a n \lg (n/k) + b > T(n)$ for $n < k$ (this replaces a similar
statement at the top of CLR page 166), and the rest of the proof
follows mostly unchanged.

This concludes the discussion of the modified quicksort's runtime; I
now continue on to discuss the insertion sort's runtime.

Once the modified $|Quick-Sort|$ has completed, the array is subject
to the condition that, if $1 \leq x < y \leq n$ and $y - x \geq k$,
then $A[x] \leq A[y]$.  For, if $x < y$ and $A[x] > A[y]$, then
clearly $x$ and $y$ must have been in the same ``final'' partition,
since all the values in any given partition are in the correct order
with respect to the values in any other partition, due to the
partitioning process of $|Quick-Sort|$.  But if $x$ and $y$ were in
the same final partition, then the separation between them must be
less than $k$, since all final partitions had fewer than $k$
elements.  Thus, any two elements separated by $k$ or more cells must
be in the correct final relative order.

The rest of the insertion sort argument is identical to that from
1(a); I copy it here (modified ever so slightly: $2k$ has become $k$,
and some extraneous material has been replaced with ellipses) for the
benefit of the grader:

\begin{quotation}
For reference, I include the pseudocode for $|Insertion-Sort|$ here.
\begin{program}
|Insertion-Sort|(A)
\quad\tab \FOR j \gets 2 \rdots |Length|(A)
              |key| \gets A[j]
              i \gets j - 1
              \WHILE i > 0 \text{and} A[i] > |key|
                    A[i+1] \gets A[i]
                    i \gets i - 1
                    \untab%
              A[i+1] \gets |key|
              \untab%
\end{program}


\dots  In other words, for any $1 \leq x < y \leq n$ such that $y
- x \geq k$, $A[y] \geq A[x]$ [\dots].  In addition, the execution of
$|Insertion-Sort|$ will never invalidate this condition, since an
element will never be moved {\em away} from its ``correct'' position,
and thus this ``maximal unordered separation'' is nonincreasing.

Thus, if $j > k$, then $A[j-k] \leq A[j]$, and so the inner loop
will terminate after, at most, $k$ iterations, since the condition
$A[i] \leq |key|$ will be reached after at most $k$ iterations.  If
$j \leq k$, then clearly the inner loop will terminate after, again,
at most $k$ iterations, since the condition $i = 0$ will be reached
after $j$ iterations.  Thus, for any given $j$, the inner loop will
execute {\bf at most} $k$ iterations before terminating.

Since the outer loop's body is executed exactly $n-1$ times, and each
iteration takes at most $k + c = O(k)$ steps, the whole [insertion
sort] algorithm runs in at most $O(kn)$ steps.
\end{quotation}

Thus, the two phase sorting algorithm runs in
$O(n \lg (n/k)) + O(nk) = O(nk + n \lg (n/k))$ time.


\newpage


\section*{Problem 3-4}

The algorithm to do this is simple.  Basically, we go through each of
the bits in order from least significant to most significant, using
one Pull and one Combine to move all the cards with a zero in bit $i$
to the top, preserving internal order.  The result is that, after
iteration $i$, the stack is sorted by the bits 1 through $i$; hence,
after $l$ iterations, the stack is completely sorted.

Clarification:  the problem set didn't make entirely clear whether bit
1 was the most significant bit or the least significant bit.  I
assume, using the normal convention, that bit 1 is the LSB and bit $l$
is the MSB.  Hence, $|Pull|(0,1)$ will pull all of the cards with
``0'' in the LSB into stack 1.

\begin{program}
|Sort|()
\quad\tab \FOR i \gets 1 \rdots l
              |Pull|(0, i)
              |Combine|(0)
          \untab%
\end{program}

Since the for loop is executed $l$ times, this algorithm uses exactly
$l$ Pulls and $l$ Combines.  (It's also clear that the algorithm
terminates.)

The loop invariant can be expressed as: ``stack 0 is sorted, in the
order that is increasing from top to bottom, by the bits from 1 to
$i$.''  (More technically, this would be
$\forall x<y : (A[x] \ \MOD 2^i) \leq (A[y] \ \MOD 2^i)$, where $x$
and $y$ are counted from the top of the stack.)  The loop invariant
holds, for a given $i$, after the $|Pull|(0,i)$ and $|Combine|(0)$ are
executed.

In the base case: before the loop begins, $i = 0$ (implicitly) and,
since anything modulo $2^0 = 1$ is zero, the condition reduces to the
null condition.  (If, for whatever reason, positing that $i = 0$
before the loop doesn't seem reasonable, one can make the base case
the point after the first iteration is executed.  Then $i = 1$, and
the algorithm has executed $|Pull|(0, 1)$, $|Combine(0)|$.  Thus, all
of the cards with ``0'' in the LSB are above those with ``1'' in the
LSB on stack 0.  Thus, the loop invariant holds.)

The inductive hypothesis is: at the beginning of iteration $i$, stack
0 is sorted by the bits from 1 to $i-1$.  After the Pull is executed,
stack 0 contains all the cards with a ``1'' in bit $i$, and stack 1
contains all the cards with a ``0'' in bit $i$; thus, every card in
stack 0 is greater than every card in stack 1, when considering bits 1
through $i$.  In addition, since Pull preserves the order of the
cards, each stack is internally sorted by bits 1 to $i-1$.  After the
Combine is executed, all of the cards with a ``0'' in bit $i$ have
been placed on top of the cards with ``1'' in bit $i$, and the order
of the cards has been preserved with respect to the lower-order bits.
Hence, at the end of the iteration, stack 0 is sorted by the bits from
1 to $i$.

At the end of the loop, the loop invariant is ``stack 0 is sorted by
the bits from 1 to $l$'', and bits 1 through $l$ are all of the bits
on the cards; thus, at the end of the loop, the postcondition ``stack
0 is sorted by all of the bits on the cards'' is satisfied.  Thus, the
algorithm is correct.

\newpage


\section*{Problem 3-5}

Assume (for purposes of contradiction) that, for arbitrary k, sorting
an input sequence of n/k subsequences of k elements each, such that
the elements in a given subsequence are all smaller than the elements
in the succeeding subsequence, takes $o(n \lg k)$ time.  Then, setting
$k = n$, sorting an unordered sequence of n elements takes
$o(n \lg n)$ time.  But this contradicts the lower bound of
$\Omega(n \lg n)$ on comparison-based sorting of an unordered
sequence.  Thus, we can say that, for arbitrary k, sorting this
partially sorted array takes at least $\Omega(n \lg k)$ time.

Now, to prove that the lower bound is tight, I present a simple
algorithm which runs in $\Theta(n \lg k)$ time:

\begin{program}
|Sort-Partially-Sorted|(A, k)
\quad\tab \FOR i \gets 1 \rdots \frac{|Length|(A)}{k}
              |Quicksort|(A, ik-k+1, ik)
          \untab%
\end{program}

The loop invariant is the condition ``all elements between 1 and ik
are sorted''.  This is clearly the case at the outset (where $i=0$),
since there are no elements between 1 and 0.  The inductive
hyptothesis is that, at the beginning of an iteration, all elements
from 1 to $(i-1)k$ are sorted, and all elements from $(i-1)k+1$ to
$ik$ are greater than all elements from 1 to $(i-1)k$.  The quicksort
sorts all the elements from $(i-1)k+1$ to $ik$, so at the end of the
iteration, all elements from 1 to $ik$ are sorted.

Since the for loop body is executed exactly n/k times, the algorithm
must halt.

Since the quicksort runs in $\Theta(k \lg k)$ time, and is executed
n/k times, the algorithm takes
$\Theta(\frac{n}{k} k \lg k) = \Theta(n \lg k)$ time.

Thus, in conclusion, the lower bound on this sorting problem is
$\Omega(n \lg k)$ time.

As for the specific examples requested: if $k = \sqrt{n}$, the lower
bound is $\Omega(n \lg \sqrt{n}) = \Omega(n \lg n)$ time. 
If $k = \lg n$, the lower bound is $\Omega(n \lg \lg n)$ time.
If $k = 2$, the lower bound is $\Omega(n)$ time.

\newpage


\section*{Problem 3-6}

Let us assume that there exists an algorithm which computes the convex
hull of a set of points in $o(n \lg n)$ steps.  Then we can construct
a sorting algorithm to sort an array of $n$ numbers thus:

\begin{program}
|Convex-Hull-Sort|(A)
\quad\tab \FOR i \gets 1 \rdots |Length|(A)
              S[i].x \gets A[i]
              S[i].y \gets A[i]^2
          \untab%
          B = |Compute-Convex-Hull|(S)
          \FOR i \gets 1 \rdots |Length|(A)
              A[i] \gets B[i].x
          \untab%
\end{program}

By construction, every point in S is on the parabola $y = x^2$.  Since
$y = x^2$ is a convex curve, the set of boundary points of the convex
hull of S is S itself.  Thus B contains all the points of S.  Also, by
the formulation of the convex hull problem, the first cell of B
contains the vertex with the smallest x-coordinate, and the subsequent
cells contain the elements of S, proceeding in a counter-clockwise
direction.  Since $y = x^2$ is convex up, this will result in the
x-coordinates of the elements of B being in nondecreasing order.
Thus, since the x-coordinates of B are the original elements of A,
copying the x-coordinates of B into A gives a sorted array consisting
of the original elements of A.  Thus, this is a correct sorting
algorithm.

The for loops are executed exactly $n$ times each;
$|Compute-Convex-Hull|$ is guaranteed to terminate by construction.
Thus, $|Convex-Hull-Sort|$ terminates.

Each of the for loops takes $\Theta(n)$ time; $|Compute-Convex-Hull|$
takes $o(n \lg n)$ time by construction.  Since
$\Theta(n) = o(n \lg n)$, $|Convex-Hull-Sort|$ takes $o(n \lg n)$
time.

Clearly, now, we have a contradiction:  sorting has a lower bound of
$\Omega(n \lg n)$ time, but $|Convex-Hull-Sort|$ takes $o(n \lg n)$
time.  Thus, the initial assumption is false; thus computing a convex
hull has a lower bound of $\Omega(n \lg n)$ steps.

\newpage


\end{document}
