\documentclass[12pt]{article}

\begin{document}
\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2007 \\
	\rm
	Homework 2a\\
	Due Thursday, January 25
\end{center}

Please use \LaTeX\ to typeset your solutions to this assignment.

\begin{enumerate}
	
\item \textbf{ [20 Points] Curly, Mo, and Larry's Totally Excellent (?) Sorting Algoithm!} Professors
Curly, Mo, and Larry of the Pasadena Institute of Technology
 have proposed the following sorting algorithm:
First sort the first two-thirds of the elements in the array. Next 
sort the last two thirds of the array.  
Finally, sort the first two thirds again.  (Notice that this
algorithm the algorithm is similar to Mergesort except that it uses
three recursive calls rather than two and there is no merging step!  As a consequence, this algorithm is very easy to implement!)  Here's the code:
\small
        \begin{tabbing}
        Stooge-sort ($A$,$i$,$j$) \\
        \textbf{begin}\\
        \ \ \ \ \ \= {\bf if} $A[i] > A[j]$ {\bf then} \\
                  \> \ \ \ \ \ {\bf swap} $A[i]$ and $A[j]$ \\
                  \> {\bf if} $i+1 \geq j$ {\bf then} \\
                  \> \ \ \ \ \ {\bf return} \\
                  \> $k = \lfloor (j-i+1)/3 \rfloor$. \\
                  \> Stooge-sort$(A,i,j-k)$ \ \ \ \ \ \= {\bf Comment:} Sort first two-thirds. \\
                  \> Stooge-sort$(A,i+k,j)$ \> {\bf Comment:} Sort last two-thirds.\\            
                  \> Stooge-sort$(A,i,j-k)$\> {\bf Comment:} Sort first two-thirds again! \\     
        \textbf{end}
        \end{tabbing}
\normalsize
        \begin{enumerate}

			
                \item Find a recurrence relation for the worst-case running time of Stooge-sort.  To simplify your recurrence relation, you may assume  each of the recursive calls is on a portion of the array that is \emph{exactly} two-thirds the length of the original array.

                \item Next, solve the recurrence relation using the 
                work tree method.  \textbf{Show all of your work.}  Do not use the ``Master Theorem'' in the book.  In your analysis, it will be 
                convenient to choose $n$ to be $c^{k}$ for some fixed
                constant $c$. (For example, we used $c=2$ when
                 analyzing Mergesort.  Here you will want to
                use a different value of $c$.  The value of $c$ that you choose might not even be an integer!  This may seem a bit strange, but it allows us to significantly simplify the analysis!)
                                 
                \item We made several simplifying assumptions:  The array could be divided perfectly into thirds and that the length of the array was a power of $c$ which wasn't even an integer.  Explain as clearly and convincingly as you can why the asymptotic running time of the algorithm remains the same even when these simplifying assumptions do not hold.

                \item How does the worst-case running time of Stooge-Sort 
                compare with the worst-case running times of the other sorting algorithms that we've seen so far?
        \end{enumerate}
\end{enumerate}

\end{document}