\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{\ML}{{\tt MANLIST}}
\newcommand{\WL}{{\tt WOMANLIST}}
\newcommand{\WR}{{\tt WOMANRANK}}
\newcommand{\MR}{{\tt MANRANK}}
\newcommand{\QU}{{\tt QUEUE}}
\newcommand{\PQU}{{\tt POPQUEUE}}
\newcommand{\AQU}{{\tt ADDTOQUEUE}}
\newcommand{\MM}{{\tt MANMATE}}
\newcommand{\WM}{{\tt WOMANMATE}}
\newcommand{\MLP}{{\tt MANLASTPROP}}
\newcommand{\NIL}{{\tt NIL}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Problem Set 2\\ Solutions}
\end{center}
\ben
\item Illustrate the operation of PARTITION(A,1,12) on the array
\[ A=(13,19,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.)
\So Using the class version we have $p=1,q=12$ and an auxilliary array
$B$ of length $12$. We initialize $left=1$, $right=12$. We first
set $x=10$, the pivot element. Now for $j=1$ to $11$ we either
put $A(j)$ as $B(left)$ and increment $left$ or as $B(right)$ and
decrement $right$, depending on whether $A(j)\leq x$ or not.
Here is what happens near the start:
\begin{center}
\begin{tabular}{rrrr}
j & newB & left & right \\
1 & B[12]=13 & 1 & 11 \\
2 & B[11]=19 & 1 & 10 \\
3 & B[1]=9 & 2 & 10
\end{tabular}
\end{center}
etc.,
after $j=11$ we get
\[ B=(9,5,8,7,4,2,6,8,11,12,19,13) \]
and now we have the left and right pointer with value $8$ so
we take our pivot value $10$ (note that we saved it so it wouldn't
be overwritten!) and make it $B[8]$, its correct position, giving
\[ B=(9,5,8,7,4,2,6,10,11,12,19,13) \]
We then reset the $A$
vector to the $B$ vector and we return
the value $8$. In {\tt QUICKSORT[1,12]} we would now recursively
{\tt QUICKSORT} the first seven positions and the final four positions.
\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!)
\So
Let $L(n) = p(n) + L(\ell) + L(r)$.
\\ $L(1) = 0$.
\\ If $n$ is odd, $\ell = \frac{n-1}{2} = r$, thus
\[ L(n) = p(n) + 2L(\frac{n-1}{2}).\]
\\ W.l.o.g. If $n$ is even, $\ell = \lceil \frac{n-1}{2}\rceil$ and
$r = \lfloor \frac{n-1}{2} \rfloor$.
\[ p(n) = n-1 \]
\begin{center}
\begin{tabular}{rclcrclcrcl}
L(1023) &=& 1022 &+& 2L(511) &=&1022 &+& 2*3586 &=& 8194\\
L(511) &=& 510 &+& 2L(255) &=& 510 &+& 2*1538 &=& 3586\\
L(255) &=& 254 &+& 2L(127) &=& 254 &+& 2*642 &=& 1538\\
L(127) &=& 126 &+& 2L(63) &=& 126 &+& 2*258 &=& 642\\
L(63) &=& 62 &+& 2L(31) &=& 62 &+& 2*98 &=& 258\\
L(31) &=& 30 &+& 2L(15) &=& 30 &+& 2*34 &=& 98\\
L(15) &=& 14 &+& 2L(7) &=& 14 &+& 2*10 &=& 34\\
L(7) &=& 6 &+& 2L(3) &=& 6 &+& 2*2 &=& 10\\
L(3) &=& 2 &+& 2L(1) &=& 2 &+& 2*0 &=& 0\\
L(1) &=& 0
\end{tabular}
\end{center}
{\tt Note:} We have to work {\em backwards} to get $L(1023)$,
doing $L(1),L(3),L(7)\cdots$ in that order.
\item You wish to sort five elements, denoted $a,b,c,d,e$. {\em Assume}
that you already know that $a** 32 = 2^5$. From the
Decision Tree Lower Bound he will need more than $5$ further questions.
\item Illustrate the operation of {\tt COUNTING-SORT} with $k=6$ on
the array $A=(6,0,2,2,0,1,3,4,6,1,3)$.
\So We start with $C[0\cdots 6]$ all zeroes. We go through $A$,
incrementing $C[A[i]]$, at the end of which $C[j]$ gives the number
of $j$'s in $A$, so it is $2,2,2,2,1,0,2$. Then from $j=1$ to $6$
we set $C[j]\leftarrow C[j]+C[j-1]$ and now $C$ has the cumulative
sums $2,4,6,8,9,9,11$. Now we work our way down the array $A$:
\\ $A[11]=2$ and $C[2]=6$ so we set $B[6]=2$ and reset $C[2]=5$.
\\ $A[10]=3$ and $C[3]=8$ so we set $B[5]=8$ and reset $C[3]=7$.
\\ $A[9]=1$ and $C[1]=4$ so we set $B[4]=1$ and reset $C[1]=3$.
\\ $A[8]=6$ and $C[6]=11$ so we set $B[11]=6$ and reset $C[6]=10$.
\\ $A[7]=4$ and $C[4]=9$ so we set $B[9]=4$ and reset $C[4]=8$.
\\ $A[6]=3$ and $C[3]=7$ so we set $B[7]=3$ and reset $C[3]=2$.
\\ That last one was the clever one. Because $C[3]$ had earlier
been decremented we are putting the second three into the appropriate
empty space.
\\ $A[5]=1$ and $C[1]=3$ so we set $B[3]=1$ and reset $C[1]=2$.
\\ et cetera. At the end $B$ is $0,0,1,1,2,2,3,3,4,6$, the sorted
output.
\item You are given a Max-Heap with $n$ entries. Assume all entries
are distinct. Your goal is to find the {\em third largest} entry.
One way would be to {\tt EXTRACT-MAX} twice and then {\tt MAXIMUM}.
How long does this take? Find a better (by which we always mean
faster for $n$ large) way.
\So As {\tt EXTRACT-MAX} takes $O(\lg n)$ and {\tt MAXIMUM}
takes $O(1)$ that method would take $2\cdot O(\lg n)+O(1)=O(\lg n)$
steps. Better: The third largest is (previous problems!) one of
$A[1]\cdots A[7]$. Sort those seven in $O(1)$ time and take the third.
\een
\end{document}
**