\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 182b\\
	Spring 2011\\
	\rm
	Homework 4, Due  Wednesday, February 16  \\
\end{center}

\begin{enumerate}

\item  \Points{20} \Name{The Wall Problem Revisited.}
Prof.~I.~Lai of the Pasadena Institute claims that the online algorithm that we saw in class for the robot ``Wall Problem'' would work just as well if we got rid of the nuisance window and simply did the sweeping step.  Show that he's wrong (as usual) by showing that without the nuisance window, there exist request sequences for which the algorithm does \emph{asymptotically} worse than $\sqrt{n}$ times optimal.

\item  \Points{25} \Name{The Wall Problem ReRevisited!}
Consider the Wall Problem again.  Now assume that all of the rectangles are squares.   As before, the robot cannot see an obstacle until it touches it.  You may assume that when the robot touches a square, it can immediately detect the distance to the the corners to its north and south.  You should also assume that square obstacles may straddle the goal line.   Show that a simpler algorithm than the one we examined in class can achieve a \emph{constant}  competitive ratio in this case (rather than $O(\sqrt{n})$ ratio)!  Your algorithm and its competitive analysis should be described clearly and you should give the best possible constant competitive ratio that you can find.

 \item \Points{15} \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{25} \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 do not require FINDs.
Show that the total running time is now
asymptotically even better than $\Theta(n \log^{*} n)$.

  \item \Points{20} \Name{Double-Rotations are the Secret to All Happiness!}
  Recall that splay trees use two types of double-rotation (``zig-zig'' and ``zig-zag'') and one
  type of single-rotation (``zig'').  Using these rotation rules, we were able to show that any 
  sequence of $n$ tree operations (such as \textsc{Insert}, \textsc{Find}, and \textsc{Delete})  can take at most $O(n \log n)$ time.  Show that 
  if we simply used a sequence of standard single-rotations to splay a node to the root when we perform a tree operation then
  there exists a sequence of $n$ tree operations that take take $\Omega(n^2)$ time. 
  (Using just \textsc{Insert} and \textsc{find} as your tree operations will
  suffice to show this.)  Aha!  Double-rotations really are the \emph{secret to all happiness}!

\end{enumerate}
\end{document}

