\documentclass[11pt]{article}
\usepackage {amsmath}
\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}{..}
  \DeclareMathOperator*{\argmin}{argmin}
  \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, 2nd edition, 2023}\\
\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 pseudocode 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 $\textsf{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 $\textsf{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). 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 \index{subject}{van Emde Boas tree} \emph{van Emde Boas tree} (vEB tree) supports insertions, deletions, and \emph{predecessor queries} for values in the interval $[1 \ltdots n]$ in $O(\log \log n)$ time. 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 the balanced search tree of Lemma 3.1 to solve range minimum queries for semi-infinite intervals $(-\infty \ltdots i]$.
\item \label{exe:select}Prove Theorem 3.3. 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.\index{subject}{four Russians technique}
\item \label{exe:fast_rank_select_build}Show how to reduce the preprocessing time in Theorems 3.2 and 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 Example 3.2 Concatenate bitvectors $B_r$, $B_v$, and $B_w$.
Give formulas to implement the example queries in
Example 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\break $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{sect:kmer} for
an analogous analysis.
\item \label{exe:rangelistextended}
Show how to efficiently implement the operation
$\mathtt{rangeListExtended}\break (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.
\item \label{exe:linearhashtable} 
In the proof of Lemma~3.17, show that insertions and deletions take expected $O(1)$ time. 
\item \label{exe:perfhashquadratic} 
In the proof of Lemma~3.18, show how to implement checking that there is no collision in (expected) linear time and linear space. 
\item \label{exe:lemma:perfhashlinear}
Show how to reduce the space used by the data structure from Lemma~3.19 to $O(n)$ bits while keeping the same construction and query times. \emph{Hint.}  Represent vectors $G$ and $T$ using bitvectors augmented with rank and select support. 
\item Show how to implement an approximate membership data structure which uses space $O(n(1+\log (1/p))$ using perfect hashing and universal hash functions. \emph{Hint:} use the construction from the previous exercise, a universal hash function, and bit-packing. 
\item \label{ex:Rabin-Karp}Show that rolling Karp--Rabin hashing is universal. 
\item \label{ex:slidingwindowminima} Develop an alternative linear time algorithm for the sliding window minima problem discussed in the context of minimizers. In this problem, you are given an array $A[1..n]$ of values and the window length $w$, and you should compute $\argmin_{j \in [i..i+w-1]} A[j]$ for each $1\leq i \leq n-w+1$. \emph{Hint.} When sliding the window from left to right, maintain in a linked list all pairs $(i,A[i])$ that can still become minima of some future window. The leftmost value in the list should be the minimum of the current window (essentially this list should match the rightmost path of the corresponding Cartesian tree).   

\end{enumerate}

\end{document}  