\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\ah}{\alpha}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\NIL}{{\tt NIL}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Problem Set 2}
\\ Due Thursday, September $19$ in Recitation
\end{center}
\begin{quote}
He who learns but does not think is lost. He who thinks but does not
learn is in great danger. -- Confucius
\end{quote}
\ben
\item Illustrate the operation of PARTITION(A,1,12) on the array
\[ A=(13,29,9,5,12,8,7,4,11,2,6,10) \]
(You may use either the text's program or the version given in class, but
please specify which you are using.)
\item Let $L(n)$, (``L'' for lucky) denote the number of comparisons that
quicksort does if each time it is applied the pivot lies in the precise
center of the array. For example, applying quicksort to an array of
length $31$, say $A(1)\cdots A(31)$
objects, there would be $30$ comparisons (between $A(31)$ and all the other
$A(j)$) and then $A(31)$ would end up in the $16^{th}$ place and there
would be two recursive calls to quicksort on arrays each of size $15$.
Find the {\em precise} value of $L(1023)$. (Hint: thats one less than 1024!)
\item You wish to sort five elements, denoted $a,b,c,d,e$. {\em Assume}
that you already know that $a