\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\begin{document}

\begin{center}
\textbf{Advanced Algorithms} \\
Takehome Exam 1 \\
Spring 2002
\end{center}

\begin{itemize}
  \item This exam is due no later than 5 PM on Wednesday, March 6. 
Please give the exam to Ran or slide it under his office door by that
time.

  \item Please read over the exam slowly and carefully as soon as
possible.  If you have questions about interpretation or believe that
anything is unclear, please talk to Ran about it early.

  \item You may use your class-notes but no other resources (written,
living, or otherwise) are permitted.

  \item The goal of this exam is two-fold:  To review some key concepts
that we've covered in the course so far and also to show you some neat
new ideas.  Given enough time to take the exam, I hope that you will find
it fun!

 \item The \LaTeX source for this exam is posted at the usual place.
\end{itemize}


\begin{enumerate}
  \item \textbf{[20 Points]  The Absent-Minded Professor.}
Professor Juan I. Dalean of the Massachusetts Institute of Zymurgy walks
out of his building one evening.  Unfortunately, he can't remember if he
parked his car up the street or down the street.  He wishes to find his
car using an online algorithm which is competitive with an
optimal offline algorithm.  

More precisely, imagine that Professor Dalean is currently at a given
point on the line (the street).  The car is parked someplace on the line
some finite distance away from Dalean, to his right or to his left.  An
optimal offline algorithm would know the location of the car and would
proceed directly there.  An online algorithm doesn't know the position
and must therefore search for it.  The online algorithm is
$k$-competitive if it eventually finds the car and traverses a distance
no larger than $k$ times the distance traversed by the online algorithm.

Find a competitive online algorithm for this problem and carefully show
that competitive ratio is 9.


\item \textbf{[40 Points] Lazy Binomial Heaps.}
Recall that a priority queue is an abstract data type which supports
operations INSERT, FIND-MIN, and DELETE-MIN.  The operation INSERT
inserts an integer into the set, FIND-MIN returns the smallest integer in
the set, and DELETE-MIN removes the smallest integer from the set.
The classical data structure for this abstract data type is a heap.
Recall that a heap is a height-balanced binary tree in which each node is
stricly smaller than its descendants.  (\textbf{Throughout this problem,
we assume for simplicity that there are no duplicate values being
stored.}) Recall that in a heap  FIND-MIN takes
$O(1)$ time since the minimum element is at the root.   INSERT and
DELETE-MIN take $O(\log n)$ time.  

In some cases it is convenient to be able to take the union of two
priority queues.  Heaps are not a great data structure in this case,
since taking two heaps of total size $n$ and merging them into one
heap takes $\Theta(n)$ time.  In this problem we will investigate a very
elegant data structure called a \emph{lazy binomial heap} which supports
operations INSERT, FIND-MIN, and UNION in $O(1)$ \emph{amortized time} and
DELETE-MIN in $O(\log n)$ \emph{amortized time}.  Thus, any sequence of
$n$ operations of which
$n-k$ are INSERT, FIND-MIN, and UNION operations and $k$ are DELETE-MIN
operations will take a total of $O(n-k + k \log n)$ time.  Notice that
this ranges between $O(n)$ and $O(n \log n)$ depending on $k$.

First, we define a \emph{binomial tree} recursively
as follows:  A single vertex is a binomial tree of type 0.  A binomial
tree of type $i$ is formed by taking two binomial trees of type $i-1$
and making the root of one of them point to the root of the other.
For example, Figure~1 shows binomial trees of types 0, 1, 2, and 3,
respectively:
\begin{figure}
\begin{center}
\epsfig{file=binomial_trees.eps, height = 1.5in}
\end{center}
\caption{Four binomial trees.  From left to right, binomial trees of types
0, 1, 2, and 3.}
\end{figure}

If you look at the number of nodes at each level of a binomial tree,
you'll see where the name comes from! 
Notice also that a binomial tree of type $r$ has exactly $2^r$ nodes in
it.  
In addition, the root of the binomial tree has in-degree $r$.
We assume that each node in a binomial tree stores its in-degree. 
Notice that since only parent pointers are kept,
each node has just 1 pointer to maintain.  We'll assume that the
root points to itself.

A \emph{lazy binomial heap} is just a linked list in which each of the
nodes is the root of a binomial tree and the nodes in each binomial tree
satisfy the heap property (that is, each node is strictly smaller than its
descendants). In addition, the lazy binomial heap maintains a pointer to
the minimum element.  Notice that this element is always a root node of
one of the binomial trees in the linked list.  We also keep track of the
size of the lazy binomial tree (the number of nodes it contains).
Figure~2 shows an example of a lazy binomial
heap.  This heap happens to comprise 4 binomial trees.  Notice that the
binomial trees in the lazy binomial heap are in no particular order.
\begin{figure}
\begin{center}
\epsfig{file=binomial_heap.eps, height = 1.5in}
\end{center}
\caption{A binomial heap containing 4 binomial trees.}
\end{figure}

Here are how each of the operations works in a lazy binomial heap:
\begin{description}
  \item[NEW-HEAP:]  This operation takes no arguments and returns
   a pointer to a new heap (just a null pointer).  The size of the heap
is set to 0.

  \item[INSERT:]  This operation takes the pointer to a particular lazy
binomial heap
  and an integer value to insert in that heap.  It constructs a new
binomial tree
  of type 0 which, recall, is just a single node.  This node stores the
  given integer value.  The new binomial tree is inserted someplace in
the lazy binomial heap (either at the beginning or the end, for example),
the pointer to the minimum element is updated if necessary, and the
size of the lazy binomial heap is incremented by 1.

  \item[FIND-MIN:]  This operation takes the name of the particular lazy
binomial heap and returns the smallest element in that heap.  Since we
are keeping a pointer to that element, this is fun and easy!

  \item[UNION:]  This operation takes the names of two lazy binomial
heaps and merges them into one lazy binomial heap.  To do so, it appends
one of the lazy binomial heaps onto the end of the other, updates the
minimum pointer, and computes the size of the new structure by
adding the sizes of the two original binomial heaps.

  \item[DELETE-MIN:]  This operation deletes the minimum element 
from the specified lazy binomial heap as follows:
  \begin{enumerate}
    \item Use the pointer to the minimum element to find the minimum.
    Remove that element and return it.  

    \item The removal of that element caused its binomial tree to break
up into a number of smaller binomial trees.  Add those trees to the lazy
binomial heap.  That is, each of those new trees is added to the list of
roots which make up the lazy binomial tree.

     \item Clean up the lazy binomial heap by repeatedly linking
two binomial trees of the same type into a larger binomial tree until
all the binomial trees in the heap are of distinct types (recall the
definition of ``type'' above).
To facilitate this cleanup phase, we begin by allocating an array $A$
with indices $0$ through $\log s$ where $s$ is the size of the lazy
binomial heap.  We initialize this array to be empty.  Then, we traverse
the linked list of binomial trees one-by-one.  For each binomial tree in
the list, if the type of the tree is $r$ we place the tree in location $r$
of array
$A$.  If that location already contains a previously inserted binomial
tree of type $r$, those two binomial trees are merged into a new binomial
tree of type $r+1$.  (To maintain the heap property, the binomial tree
with the larger root value points to the binomial tree with the smaller
root value.)  This  new tree is then placed in location $r+1$ of the
array.  If there is already a binomial tree of in-degree $r+1$ in that
location, the merging process may continue.  

  \item After all of the binomial trees have been inserted into the
array, the array contains at most one binomial tree of each type.
These binomial trees are then threaded together via a new linked list
which comprises the new clean lazy binomial heap.  

  \item Finally, this new lazy binomial heap is traversed to set the new
pointer to the minimum element.

  \end{enumerate}

  
\end{description}

Here are your tasks:
\begin{enumerate}

  \item Briefly explain why each of the operations NEW-HEAP, INSERT,
FIND-MIN, and UNION take $O(1)$ actual time.

  \item Briefly explain what is ``binomial'' about a binomial tree.

  \item Briefly explain why a binomial tree of type $r$ has $2^r$ nodes.

  \item In the DELETE-MIN operation, after the minimum element is removed,
 its binomial tree became fragmented.  Explain briefly why all of the
fragments have sizes which are powers of 2 and can thus be considered
binomial trees themselves.

  \item Now, let $\ell$ denote the number of binomial trees in the 
linked list immediately after the minimum element was removed and the
resulting fragments were added to the list.  Show that the entire cleanup
phase described in step (c) of the DELETE-MIN operation can be performed
in $O(\ell)$ time.  Notice that some binomial trees may merge several
times while others might just get plopped in a location of the array and
stay there.  Therefore, your argument here will require an amortized
analysis.  Prove the $O(\ell)$ time bound \textbf{three different ways}: 
using aggregate analysis, the accounting method, and the potential method.


  \item Explain briefly why the resulting ``cleaned up'' lazy binomial
heap contains at most $\log n$ binomial trees in its linked list (where
$n$ is the total number of heap operations performed and thus an upper
bound on the number of nodes among all the heaps.)

  \item Now, define an appropriate potential function and show that 
the amortized cost of the entire DELETE-MIN operation is $O(\log n)$.

  \item Finally, show that under this potential function, the amortized
costs of all of the other operations are still $O(1)$.
(In the event that the potential function you used in the previous part
doesn't quite work here, think about modifying the potential function
slightly.)
 
  \item Conclude that this is a very nifty data structure and an elegant
piece of analysis.  Eat chocolate and/or take a break to celebrate.
\end{enumerate}


\item \textbf{[40 Points] Optimal Sorting on a 2-Dimensional Mesh!}
        \begin{enumerate}
                \item Recall that we argued in class that every sorting
                algorithm on a $\sqrt{n} \times \sqrt{n}$ mesh
                has worst case running time of $\Omega(\sqrt{n})$ 
                (that is, asymptotically $\sqrt{n}$ or worse.)
                Explain briefly why this is true.

                \item Now we'll develop an asymptotically optimal
                sorting algorithm for a $\sqrt{n} \times \sqrt{n}$
                mesh.  That is, we'll find an algorithm that runs
                in time $O(\sqrt{n})$.  We'll call this algorithm
                ``Divsort''.  
                The Divsort algorithm will sort the input into a snakelike
                order (just like the ordering that Shearsort gave us).
                For simplicity, we'll assume that $\sqrt{n}$ is a power of 2.

                Divsort starts by calling itself to recursively
                Divsort each the four quadrants of the mesh in a
                snakelike order.  Second, Divsort sorts the rows
                of the mesh in alternating order 
                (increasing, decreasing, etc. as in
                Shearsort).  Third, the columns of the mesh are sorted from top
                to bottom (again like in Shearsort).  Finally, we
                treat the overall snakelike path of length $n$ as one 
                long array and we do $4 \sqrt{n}$ clock steps of odd-even
                sorting on this array.  (Actually, only $2 \sqrt{n}$
                steps are needed, but this makes the proof more
                complicated.  If it makes your life easier, you can
replace the 4 with a 6 or any other fixed constant that you like.)
                Prove that Divsort correctly sorts any input set.

                \item Set up a recurrence relation for Divsort and
                unwind it to show that the running time is indeed 
                $O(\sqrt{n})$.  Show your work in detail.  Pretty neat!!
        \end{enumerate}
\end{enumerate}
\end{document}