\documentclass[12pt]{article}
\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}
\newcommand{\myspan}{\mbox{span}}

\usepackage{geometry}

\begin{document}
	\begin{center}
	\bf
	Advanced Topics in Algorithms \\
	Computer Science 181b\\
	Spring 2012\\
	\rm
	Homework 4 ``Lite'', Due  Wednesday, February 15  \\
\end{center}

\begin{enumerate}

 \item \Points{20} \Name{Union-Find with Partial Path Compression.}
In class we examined the union-find data structure using union-by-size
and path compression.  One disadvantage of path compression is that it
is a two-phase process:  First we must ``climb'' the path to find the
root.  Then, we climb the path a second time and set the parent of each node on that path to be the root.

The famous Shmorbodian theoretical computer scientist, Professor
Y.~Woerksohaard, proposes the following simpler approach called \emph{partial path compression}:
As we ``climb'' a path from a node to the root of its tree, 
each node on the path has its parent pointer changed to point to its
grandparent.  This process can be done in just one pass as we climb up
the path.  
Professor Woerksohaard claims that this approach still allows us to perform any sequence of $n$ \textsc{MAKESET}, \textsc{\textsc{UNION}}, and \textsc{FIND} operations in time $O(n \log^{*} n)$ time.  Is this true or false?
If true, give a short but precise explanation (you may cite any part of the proof that we did in class without replicating it).  If false, give a short but precise counter-example.

  \item \Points{15} \Name{Union-Find Again.}
Consider again the union-find data structure using union-by-size and path
compression.  Assume that we will perform a sequence of $n$ \textsc{MAKESET}, \textsc{\textsc{UNION}}, and \textsc{FIND}
operations where all of the \textsc{MAKESET}s are performed before the \textsc{\textsc{UNION}}s
and all of the \textsc{\textsc{UNION}}s are done before the \textsc{FIND}s.   You should assume that the UNIONs that are performed do not require FINDs; that is, the UNIONs are invoked on the canonical nodes of each set.
Show that the total running time is now
asymptotically even better than $\Theta(n \log^{*} n)$.

  \item \Points{30} \Name{The Dynamic List Access Problem!}
 In class we looked at the MTF online algorithm for the List Access
Problem.  Specifically, we looked at the \textbf{Static} List Access
Problem where only \textsc{Find}s were allowed - there were no \textsc{Insert} and \textsc{Delete}
operations permitted in the request sequence.

Now, consider the more general \textbf{Dynamic} List Access Problem which
differs from the static version in three ways:
  \begin{enumerate}
    \item Any \textsc{Find} operation may fail.  That is, the item might not be
found.  In this case, the actual cost is $\ell + 1$ where $\ell$ was the
length of the list at the time that the \textsc{Find} was performed. 

    \item \textsc{Insert} operations are permitted in the request sequence.  An
inserted object is placed at the end of the list.  If the length of the
list prior to the \textsc{Insert} was $\ell$, then the actual cost of this
operation is $\ell + 1$.  After inserting the element at cost $\ell + 1$,
you may move it to any position earlier in the list at no cost (just like
in a successful \textsc{Find} operation).

   \item \textsc{Delete} operations are permitted in the request sequence.  The
cost of the \textsc{Delete} is simply the cost of finding the object.  (However,
the potential function changes as a consequence of the \textsc{Delete}, so a
\textsc{Delete} differs from a \textsc{Find} in this way!)
  \end{enumerate}

Describe a modification of the MTF algorithm to handle all three of these operations.
Show that when your modified MTF algorithm is applied to the Dynamic List Access Problem, it
still maintains a competitive ratio of 2.  (That is, it is 2-competitive
with respect to an optimal offline algorithm.)





\end{enumerate}
\end{document}

