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

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

\head{1390}{Algorithms}{Winter 2001}{6 February 2001}{11}

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

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

{\bf 1. (20 points) Bubblesort }

In class, we are studying a number of sorting algorithms including
selection sort, mergesort, heapsort, and quicksort.  In this problem,
we consider another well-known sorting algorithm called {\em
bubblesort}.  The following is the pseudocode for bubblesort.
\begin{tabbing}
\= $\bs(A)$\\
\> 1. \= \algfor\ \= $i \leftarrow 1$ to $n$\\
\> 2. \> \> \algfor\ \= $j \leftarrow 1$ to $n-1$\\
\> 3. \> \> \> \algif\ \= $A[j] > A[j+1]$\\
\> 4. \> \> \> \> swap elements $A[j]$ and $A[j+1]$\\
\> 5. \> \> \> \algfi\\
\> 6. \> \> \algrof\\
\> 7. \>  \algrof
\end{tabbing}

\begin{itemize}
\item[{\bf (a)}] Prove the following loop invariant for the {\em inner}\/
loop: At the end of the $j$th inner loop, $A[j+1] \ge A[k]$ for all $k \le j$.

{\bf Answer:} The proof is by induction on $j$, the number of the
iterations of the inner loop.  For the base case, we let $j = 0$ (we
can also work with $j = 1$). At the end of the $0$th inner loop, we
need to prove that $A[1] \ge A[k]$ for all $k \le 0$; this is
trivially true.

We now consider the induction step.  For the hypothesis, we assume
that at the end of iteration $\ell - 1$ of the inner loop, we have
$A[\ell] \ge A[k]$ for all $k \le \ell - 1$.  Consider iteration
$\ell$ of the inner loop.  In this iteration $A[\ell]$ is compared
with $A[\ell + 1]$ and swapped if $A[\ell] > A[\ell + 1]$.  If the
swap does not occur, then $A[\ell + 1]$ is at least $A[\ell]$ which,
by the induction hypothesis, is at least $A[k]$ for all $k \le \ell -
1$.  Thus, after the execution of this iteration of the loop, $A[\ell
+ 1] \ge A[k]$ for all $k \le \ell$.  If the swap occurs, then again
$A[\ell + 1]$ is at least $A[\ell]$.  Moreover, by the induction
hypothesis $A[\ell + 1]$ (which was previously $A[\ell]$) is at least
$A[k]$ for all $k \le \ell - 1$.  Therefore, again the desired claim
of the induction step holds.
 
\item[{\bf (b)}] State and prove a loop invariant for the outer loop.
({\em Hint:} Identify what the effect of the $i$th loop is.)

{\bf Answer:} The effect of the $i$th outer loop is that the $i$th
largest element is moved to $A[n-i+1]$.  In particular, we will show
that after the execution of the $i$th outer loop, we have $A[n - i
+1..n]$ is in sorted order and every element in $A[n-i+1..n]$ is at
least as large as any element in $A[1..n-i]$.  The proof is by
induction on $i$.  For the base, we can set $i = 1$, in which case we
need to show that after the execution of the first outer loop, $A[n] =
\max\{A[1..n]\}$.  By part~(a), we know after the execution of
iteration $n-1$ of the inner loop, $A[n] \ge A[k]$ for all $k \le
n-1$.  Thus, $A[n] = \max\{A[1..n]\}$ the desired claim follows.

For the induction step, we assume first that after the execution of
iteration $\ell - 1$ of the outer loop, $A[n-\ell+2..n]$ is in sorted
order and every element in $A[n-\ell+2..n]$ is at least as large as
$A[1..n-\ell+1]$.  Now consider the $\ell$th outer loop.  By part~(a),
after iteration $n - \ell$ of the inner loop, we have $A[n-\ell+1]$ is
at least as large as any element in $A[1..n-\ell]$.  By the induction
hypothesis, $A[n-\ell+2..n]$ is sorted and every element in
$A[n-\ell+2..n]$ is at least as large as any element in
$A[1..n-\ell+1]$.  Thus, the remaining iterations of the inner loop do
not swap any elements and we have at the end of the $\ell$th inner
loop: $A[n-\ell+1..n]$ is sorted and every element in $A[n-\ell+1..n]$
is at least as large as any element in $A[1..n-\ell]$.  This completes
the induction step.

\item[{\bf (c)}] Using part~(b), show that the algorithm is correct.

{\bf Answer:} By part~(b), after iteration $n$ of the outer loop,
$A[1..n]$ is sorted.  This shows that the algorithm is correct.

\item[{\bf (d)}] In terms of $n$, how many times is line $3$ executed
in the worst case?  What is the worst-case asymptotic bound on running
time for \bs.

{\bf Answer:} Line 3 is executed once for every iteration of the inner
loop.  The inner loop is executed $n-1$ times for every iteration of
the outer loop.  The outer loop is executed $n$ times.  Therefore,
line 3 is executed $n(n-1) = n^2 - n$ times.  This holds for {\em
any}\/ input instance.

Line 1 is executed $n$ times, line 2 $n(n-1)$ times, and line 4 at
most $n(n-1)$ times.  Therefore, the worst-case running time is
$\Theta(n^2)$.

\item[{\bf (e)}] In terms of $n$, how many times is line $3$ executed
in the best case?  What is the best-case asymptotic bound on running
time for \bs.

{\bf Answer:} As mentioned above, line 3 is executed $n(n-1)$ times
regardless of the input instance.  Moreover, line 1 is executed $n$
times, and line 2 $n(n-1)$ times for every instance.  In the best
case, line 4 is never executed (when the if-condition never holds).
The best-case total running time is still $\Theta(n^2)$.
\end{itemize}

{\bf 2. (20 points) Towers of Hanoi} 

The Towers of Hanoi problem is a classic example of recursion.  In the
Towers of Hanoi problem, $n$ disks of different sizes are piled on a
peg in order of their size, with the largest at the bottom.  There are
two empty pegs.  The problem is to move all the disks to the third peg
by moving only one disk at a time and never placing a disk on top of a
smaller one.  The second peg may be used for intermediate moves.

The usual solution recursively moves all but the last disk from the
starting peg to the spare peg, then moves the remaining disk (the
largest one) from the start peg to the destination peg, and then
recursively moves all the others from the spare peg to the destinstion
peg.  This recursive solution is described in the following recursive
procedure.

\begin{tabbing}
\= \hanoi$(n, \start, \dest, \spare)$\\
\> 1. \= \algif\ \= $n > 0$\\
\> 2. \> \> $\hanoi(n-1, \start, \spare, \dest)$\\
\> 3. \> \> \algprint\ ``move top disk from peg '', \start, ``to peg '',
\dest\\
\> 4. \> \> $\hanoi(n-1, \spare, \dest, \start)$
\end{tabbing}

Write a recurrence for the number of moves for $n$ disks.  Solve this
recurrence.

{\bf Answer:} Let $H(n)$ denote the number of moves for $n$ disks.
From the recursive solution, we obtain 

\[
H(n) = \left\{
\begin{array}{ll}
2H(n-1) + 1 & n > 0,\\
0 & n = 0
\end{array}
\right.
\]
We use the iteration method to solve the recurrence.  Upon unraveling
the recurrence $i$ times, we obtain
\[
H(n) = 2^iH(n-i) + 2^{i-1} + 2^{i-2} + \ldots + 2^{1} + 1.
\]
Setting $i = n$, we get
\begin{eqnarray*}
H(n) & = & 2^nH(0) + 2^{n-1} + 2^{n-2} + \ldots + 2^{1} + 1\\
& = & 2^{n-1} + 2^{n-2} + \ldots + 2^{1} + 1\\
& = & 2^n - 1.
\end{eqnarray*}

{\bf 3. (20 points) Recurrences}

Find the asymptotic solution (using the $\Theta$-notation) for each of
the following recurrences.  Assume that $T(n)$ is constant for $n \le
2$.
\begin{itemize}
\item[{\bf (a)}] $T(n) = T(n/2) + 2n^2$.

{\bf Answer:} We use the Master method.  We have $b = 1, c = 2$, and
$f(n) = 2n^2$.  We obtain $E = 0$ and $n^E = n^0$.  Since $2n^2 =
\Omega(n^{0+2})$, there exists an $\eps > 0$ (for example, $\eps = 2$)
such that $f(n) = \Omega(n^{E + \eps})$.  This suggests case 3 of the
Master Theorem.  We need to check for another condition, though.  This
is whether $f(n) = O(n^{E+\delta})$ for some $\delta \ge \eps$.
Setting $\delta = 2$ confirms this condition.  Thus, we invoke case 3
of the Master theorem to obtain $T(n) = \Theta(n^2)$.

\item[{\bf (b)}] $T(n) = 81T(n/3) + n^4/3$.

{\bf Answer:} We use the Master method.  We have $b = 81, c = 3$, and
$f(n) = n^4/3$.  We obtain $E = \lg 81/\lg 3 = 4$ and $n^E = n^4$.
Since $n^4/4 = \Theta(n^4)$, we have $f(n) = \Theta(n^E)$.  Thus, we
invoke case 2 of the Master theorem to obtain $T(n) = \Theta(n^4\lg
n)$.

\item[{\bf (c)}] $T(n) = T(\sqrt{n}) + 1$.

{\bf Answer:} We cannot use the master method.  We therefore use the
iteration method here.
\begin{eqnarray*}
T(n)
& = & 1 + T(n^{1/2})\\
& = & 1 + 1 + T(n^{1/4})\\
& = & i + T(n^{1/2^i})\\
& = & \Theta(\lg \lg n) + T(2) \mbox{ (since $n^{1/2^{\lg \lg n}} = n^{1/\lg
n} = 2^{(\lg n)/(\lg n)} = 2$)}\\
& = & \Theta(\lg \lg n).
\end{eqnarray*}
We note that we iterate until $n$ comes down to $2$, rather than $1$
as we have been usually doing.  The reason we do this is that if we
repeatedly take the square root of a number bigger than $1$, we will
never obtain $1$ in a finite number of steps.  Therefore, the
recurrence is undefined below $n = 2$.  Since we know that $T(2)$ is
constant, we stop the recurrence at $2$ and derive the final result.
\end{itemize}

{\bf 4. (20 points) Stooge Sort}

Professors Howard, Fine, and Besser have proposed the following
``elegant'' sorting algorithm.
\begin{tabbing}
\= $\stooge(A, i, j)$\\
\> 1. \= \algif\ \= $A[i] > A[j]$ \\
\> 2. \> \> exchange $A[i] \leftrightarrow A[j]$\\
\> 3. \> \algif\ $i + 1 \ge j$\\
\> 4. \> \> \algreturn\\
\> 5. \> $k \leftarrow \lfloor(j - i + 1)/3\rfloor$ \hspace{1in} \=
// Round down.\\
\> 6. \> $\stooge(A, i, j-k)$ \>  // First two-thirds.\\
\> 7. \> $\stooge(A, i + k, j)$ \> // Last two-thirds.\\
\> 8. \> $\stooge(A, i, j-k)$  \>  // First two-thirds again.
\end{tabbing}
\begin{itemize}
\item[{\bf (a)}] 
Argue that $\stooge(A, 1, n)$ correctly sorts the input array $A[1..n]$.

{\bf Answer:} Here is a formal proof of the correctness of \stooge.
(For getting credit, an informal but substantial argument would
suffice.)

To prove that \stooge($A, i, j$) sorts correctly, we use induction on
$\ell = j - i + 1$.  (That is, $\ell$ is the number of elements in
$A[i.. j]$.)  For the induction basis, we consider two cases: $\ell =
1$ or $\ell = 2$, i.e., $i = j$ or $i = j -1$.  For each of these
cases, in Steps~1 and~2, $A[i]$ and $A[j]$ are exchanged if $A[i] >
A[j]$.  Also, in both cases the condition in Step~3 holds.  Therefore,
\stooge($A, i, j$) returns after having sorted $A$.

For the induction hypothesis, we assume that \stooge\ sorts correctly for all
arrays of length less than $m$, where $m > 2$.  We now show that \stooge\ sorts
correctly for all inputs of length $m$.  Since $m > 2$, the condition in
Step~3 is not true; hence \stooge\ does not return in Step~4.  Moreover, for the
discussion that follows, it does not matter whether the exchange of $A[i]$ and
$A[j]$ took place in Step~2.  So we now consider Steps~5 through~8.  The
variable $k$ is set to $\lfloor(j - i + 1)/3\rfloor$ in Step~5.  Since $j - i
+ 1 \ge 3$, $k \ge 1$; therefore, $j - i - k + 1 = m - k < m$.  Therefore, the
length of the array $A[i.. j- k]$ on which \stooge\ is called in Step~6 is less
than $m$.  By the induction hypothesis, it follows that $A[i.. j - k]$ is in
sorted order after Step~6.  Hence, $A$ has the following property: (P1) for
all $x$ in $[i.. i + k - 1]$ and $y$ in $[i+ k.. j- k]$, $A[x] \le A[y]$.  In
particular, we see that there are at least $k$ elements in $A[i+k.. j]$ that
are greater than or equal to every element in $A[i.. i+k-1]$.  Next, \stooge\
sorts $A[i + k, .., j]$.  Again, the length of the array is less than $m$.  So
we invoke the induction hypothesis and claim that after Step~7, $A[i + k.. j]$
is sorted. Since $A[i+k.. j]$ is sorted, $A$ has the following property:
(P2) $A[j-k+1.. j]$ is sorted correctly, and (P3) for all $x$ in $[i + k.. j -
k]$ and $y$ in $[j - k + 1.. j]$, $A[x] \le A[y]$.

Since the elements in indices $[i.. i+k-1]$ do not move, the following
property (that follows from~(P1)) still holds: (P4) there are at least $k$
elements in $A[i+k.. j]$ that are greater than or equal to every element in
$A[i.. i+k-1]$.  Therefore, combining with property~(P3) above, we have: (P5)
for all $x$ in $[i.. j - k]$ and $y$ in $[j - k + 1.. j]$, $A[x] \le A[y]$.
Thus, after step~6, properties~(P2) and~(P5) hold.

Finally, we apply \stooge\ on $A[i.. j -k]$.  Again the length of the array, $j -
k - i + 1$ is less than $m$.  So applying the induction hypothesis, we obtain
that $A[i.. j - k]$ is sorted correctly.  Moreover, since the indices
$[j-k+1.. j]$ are unaffected, properties~(P2) and~(P5) still hold.  We thus
obtain that the entire array $A[i.. j]$ is sorted correctly.

\item[{\bf (b)}]
Give a recurrence for the worst-case running-time of \stooge\ and a tight
asymptotic ($\Theta$-notation) bound on the worst-case running time.

{\bf Answer:} Let $T(n)$ be the worts-case running time of \stooge\ on an
array of length $n$.  Steps~1 through~5 take $\Theta(1)$ time.
Steps~6 through~8 take $T(n - k)$ time.  Since $k = \lfloor n/3
\rfloor$, $2n/3 \le n - k \le 2n/3 + 1$.  Ignoring floors and
ceilings, we can write the recurrence as
\[
T(n) = 3T(2n/3) + \Theta(1).
\]
We use the Master method.  Since $b = 3, c = 3/2$, we get $E =
\log_{3/2} 3$.  We have $f(n) = \Theta(1)$; clearly, there exists an
$\eps > 0$ (for example, $\eps = \log_{3/2} 3$) such that $f(n) =
O(n^{E - \eps})$.  We thus invoke case 1 of the Master theorem to
obtain $T(n) = \Theta(n^{\log_{3/2} 3}$.

\item[{\bf (c)}]
Compare the worst-case running time of \stooge\ with that of selection
sort, mergesort, and heapsort.  Do the professors deserve tenure?

{\bf Answer:} Since $T(n) = \Theta(n^{\log_{3/2} 3})$, and $\log_{3/2}
3 > 2$, \stooge\ is worse than each of insertion sort, merge sort,
heapsort, and quicksort.  The professors do not deserve tenure.

\end{itemize}
\end{document}
