\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts,graphicx}

\begin{document}

\begin{center} \Large
{\scshape 6.851 Advanced Data Structures (Spring'10)} \\[1ex]
{Prof.~Erik Demaine \qquad Dr.\ Andr\'e Schulz \qquad TA: Aleksandar Zlateski} \\[2ex]
\framebox{Problem 4} \quad {\em Due: Thursday, Mar.\ 4}
\end{center}

Be sure to read the instructions on the assignments section of the
class web page.

\paragraph{\boldmath Analysis partition trees.}
Prove that Matou\v{s}ek's theorem on the crossing number of fine partitions implies a  $O(n^{\frac{1}{2}+\varepsilon})$ query time for partition trees for 2d halfspace counting. \\
\emph{Hint:} Choose as size of the fine partition $r=\lceil 2(c\sqrt{2})^{(1/\varepsilon)}\rceil$, where $c\sqrt{r}$ is the bound for the crossing number.


\paragraph{\boldmath Speed up with LCP array.}\
Suppose we have a data structure RMQ, that stores an indexed sequence of integers $\{a_1,a_2,\dotsc, a_n \}$. A query $\tt{rmq}(i,j)$ returns the index of the smallest element  of  the subsequence $\{a_i,\dotsc,a_j \}$ in $O(1)$ time. RMQ can be build in $O(n)$ time.

\begin{enumerate}
\item Show how to compute the LCP array using an RMQ data structure along the DC3 algorithm for computing the suffix array in linear time. In particular, show how to compute an entry of the LCP in $O(1)$ time if we have the knowledge of the LCP array of the difference cover $\tilde T$. 
\item Use the RMQ data structure and the LCP array to speed up the search in a suffix array from $O(|P|\log |T|)$ to  $O(|P|+\log |T|)$. 
\end{enumerate}
\end{document}
