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

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

\head{1390}{Algorithms}{Winter 2001}{18 January 2001}{8}

\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 Problem Set 2 (due January 29)}
\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$.

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

\item[{\bf (c)}] Using part~(b), show 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.

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

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

\item[{\bf (c)}] $T(n) = T(\sqrt{n}) + 1$.
\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]$.

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

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