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

\begin{document}

\let\epsilon=\varepsilon

\begin{center} \Large
{\scshape 6.851 Advanced Data Structures (Spring'12)} \\[1ex]
{Prof.~Erik Demaine \qquad TAs: Tom Morgan, Justin Zhang} \\[2ex]
\framebox{Problem 10} \quad {\em Due: Thursday, May\ 3}
\end{center}

Be sure to read the instructions on the assignments section of the
class web page.  Remember to keep your solutions to one page!

\paragraph{Compact balanced parentheses.}
Recall that in lecture we introduced the balanced-parentheses representation of a binary trie.  A common query when using this representation is ${\tt match}(i)$, which returns the index of the close parenthesis matching the open parenthesis at index $i$.  In this problem we will develop a compact data structure to answer these queries (though a succinct data structure is known).

\begin{enumerate}
\item Let $S$ be a string of balanced parenthesis.  Divide $S$ into blocks of size $B$.  We will call an open parenthesis \emph{far} if its matching parenthesis is in a different block.  A far parenthesis is a \emph{pioneer} if its matching parenthesis is in a different block than the matching parenthesis of the previous far parenthesis in $S$.  Prove that there are $O(|S|/B)$ pioneer parenthesis.
\item Develop and analyze a static data structure that, given a string of balanced parenthesis $S$, answers {\tt match} queries in $O(1)$ time and uses $O(|S|)$ bits of space.
\end{enumerate}

\end{document}
