\documentclass[11pt]{article}
\usepackage[margin=1.2in,a4paper]{geometry} % try also "letterpaper" instead of "a4paper"
\usepackage{enumitem} % this package is used to generate the custom chapter prefix "[Chapter number].[Exercise Number]"

%%%%%%%%%% macros %%%%%%%%%%
  \newcommand{\ltdots}{..}
  \newcommand{\Thm}[1]{Theorem~{#1}}
  \newcommand{\Ex}[1]{Example~{#1}}
  \newcommand{\Sec}[1]{Section~{#1}}  
%%%%%%%%%% macros %%%%%%%%%%

\begin{document}

%%%%%%%%%% header %%%%%%%%%%
\noindent {\sf\LARGE GENOME-SCALE ALGORITHM DESIGN} \\
\noindent {\sf by Veli M{\" a}kinen, Djamal Belazzougui, Fabio Cunial and Alexandru I. Tomescu}\\
\noindent {\sf Cambridge University Press, 2015}\\
\noindent {\sf www.genome-scale.info}\\
\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%%%%%%%%%% header %%%%%%%%%%

\section*{Exercises for Chapter 3. Data structures}

\begin{enumerate}[label=3.\arabic*]
\item \label{exe:bst_example}Give an example of a perfectly balanced binary search tree storing eight (key,value) pairs in its leaves as described in Lemma~3.1. Give an example of a range minimum query for some non-empty interval.
\item \label{exe:bst_init}Give a pseudo-code for the algorithm to construct and initialize a balanced binary search tree given the sorted keys.
\item \label{exe:dynamic_rmq}Recall how \emph{red--black trees} work. Revisit the proof of Lemma~3.1 and consider
how the tree can be maintained correctly updated for $\mathsf{RMQ}$ queries during the rebalancing operations needed if one adds the support for
$\mathtt{Insert}$ and $\mathtt{Delete}$.
\item Instead of taking the minimum among the values in Lemma~3.1 one could take a sum. If all leaves are initialized to value $1$, what question does the operation analogous to $\mathsf{RMQ}$ answer?
\item Consider the sets $V'$ and $V''$ in the proof of Lemma~3.1. The subtrees rooted at nodes in $V'$ and $V''$ induce
a \emph{partitioning} of the set of characters appearing in the interval $[l \ltdots r]$ (see Figure 3.1 from the book).
There are many other partitionings of $[l \ltdots r]$ induced by different subsets of nodes of the tree.
Why is the one chosen in the proof the minimum size partitioning? Are there other partitionings that could give the same running time?
\item \label{exe:bst_vEB}A \emph{van Emde Boas tree} (vEB tree) supports in $O(\log \log n)$ time insertions, deletions, and \emph{predecessor queries} for values in the interval $[1 \ltdots n]$. A predecessor query returns the largest element $i'$ stored in the vEB tree smaller than query element $i$. Show how the structure can be used instead of a balanced search tree of Lemma~3.1 to solve range minimum queries for semi-infinite intervals $(-\infty \ltdots i]$.
\item \label{exe:select}Prove \Thm{thm:select}. \emph{Hint.} Start as in $\mathtt{rank}$ with $O(\log^2 n)$ size blocks, but this time on arguments of $\mathtt{select}_1$. Call these \emph{source blocks} and the areas they span in bitvector $B$ \emph{target blocks}. Define \emph{long} target blocks so that there must be so few of those that you can afford to store all answers inside the corresponding source blocks. We are left with \emph{short} target blocks. Apply the same idea recursively to these short blocks adjusting the definition of a \emph{long} target block in the second level of recursion. Then one should be left with short enough target blocks that the four Russians technique applies to compute answers in constant time.
The solution to $\mathtt{select}_0$ is symmetric.
\item \label{exe:fast_rank_select_build}Show how to reduce the preprocessing time in \Thm{3.2} and \Thm{3.3} from $O(n)$ to $O(n/\log n)$, by using the four Russians technique during the preprocessing. 

\item \label{exe:wavelettree_navi}Consider the wavelet tree in \Ex{3.2}. Concatenate bitvectors $B_r$, $B_v$, and $B_w$.
Give formulas to implement the example queries in \Ex{3.2} with just the concatenated bitvector.
Derive the general formulas that work for any wavelet tree.
\item \label{exe:waveletselect}
Consider the operation $\mathtt{select}_c(A,j)=i$ that returns the position $i$ of the $j$th occurrence of character $c$ in string $A[1 \ltdots n]$. Show that the wavelet tree with its bitvectors preprocessed for constant time $\mathtt{select}_1(B,j)$ and $\mathtt{select}_0(B,j)$ queries can answer $\mathtt{select}_c(A,j)$ in $O(\log \sigma)$ time.
\item \label{exe:fingersearch}
Show that the operation $\mathtt{rangeList}(T,i,j,l,r)$ can be supported in $O(d \log (\sigma/d))$ time by optimizing the given search strategy. \emph{Hint.} After finding the left-most element in the interval, go up until branching towards the second element occurs, and so on. Observe that the worst case is when the elements are equally distributed along the interval: see \Sec{8.1} for an analogous analysis.
\item \label{exe:rangelistextended}
Show how to efficiently implement the operation $\mathtt{rangeListExtended}(T,i,j,l,r)$
which returns not only the distinct characters from $[l\ltdots r]$in $T[i\ltdots j]$, but also, 
for every such distinct character $c$, returns the pair $(\mathtt{rank}_c(T,i-1),\mathtt{rank}_c(T,j))$. 
\emph{Hint.} Observe that the enumeration of the distinct characters uses rank queries on binary sequences that 
can also be used to compute the pairs of rank operations executed for the distinct characters. 

\end{enumerate}

\end{document}  