\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]"
\usepackage{amssymb}
\usepackage{amsmath}

%%%%%%%%%% macros %%%%%%%%%%
  \newcommand{\Fig}[1]{Figure~{#1}}
  \newcommand{\Def}[1]{Definition~{#1}}  
  \newcommand{\Thm}[1]{Theorem~{#1}}
  \newcommand{\Lemma}[1]{Lemma~{#1}}  
  \newcommand{\Sec}[1]{Section~{#1}}   
  \newcommand{\Btw}[1]{Insight~{#1}}
  \newcommand{\Prob}[1]{Problem~{#1}}  
  \newcommand{\Exe}[1]{Exercise~{#1}}  
  \newcommand{\Algo}[1]{Algorithm~{#1}}
  \newcommand{\Prop}[1]{Property~({#1})}  
  \newcommand{\Cor}[1]{Corollary~{#1}}  
  \newcommand{\ltdots}{..}  
  \newcommand{\wt}{\::\:}
  \newcommand{\st}{\:|\:}  
  \newcommand{\Eq}[1]{Equation~({#1})} 
  \newcommand{\Chap}[1]{Chapter~{#1}}
  \newcommand{\Ex}[1]{Example~{#1}}     
  \DeclareMathOperator*{\argmax}{argmax}  
  \newcommand{\SA}{\ensuremath{\mathsf{SA}}}  
  \newcommand{\LCP}{\ensuremath{\mathsf{LCP}}}  
  \newcommand{\ST}{\ensuremath{\mathsf{ST}}}  
  \newcommand{\REV}[1]{\ensuremath{\underline{#1}}}  
  \newcommand{\BWT}{\ensuremath{\mathsf{BWT}}}  
  \newcommand{\DBG}{\ensuremath{\mathsf{DBG}}} % De Bruijn graph  
  \newcommand{\INTERVALFUNCTION}{\ensuremath{\mathbb{I}}}  
  \newcommand{\KL}{\ensuremath{\mathsf{KL}}}
  \newcommand{\SUS}{\ensuremath{\mathsf{SUS}}} 
  \newcommand{\SLT}{\ensuremath{\mathsf{SLT}}}     
  
%%%%%%%%%% 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 12. Compression of genome collections}

\begin{enumerate}[label=12.\arabic*]

\item \label{exe:lzdeBruijnseq} Recall from \Exe{11.7} that a $\sigma$-ary de Bruijn sequence of order $k$ is a string of length $\sigma^k+k-1$ over an alphabet of size $\sigma$ that contains as substrings all the $\sigma^k$ possible strings of length $k$. What is the number of phrases in the Lempel--Ziv parse of such a sequence? What does this tell you about the asymptotic worst-case complexity of a Lempel--Ziv parse? \emph{Hint.} Combine your result with \Lemma{12.2}.

\item Consider the solution of Exercise \ref{exe:lzdeBruijnseq}. Is the size of the Lempel-Ziv parse of a string a good approximation of its Kolmogorov complexity, roughly defined in \Sec{11.3.5}? 

\item \label{exe:lzfact_suffix_tree} Show how to build in linear time the augmented suffix tree used in \Sec{12.1.1}.  

\item \label{exe:lzfact_build_R} Show how to build the vector $R$ described in \Sec{12.1.2} in $O(n\log\sigma)$ time and in $O(n\log\sigma)$ bits of space.  

\item \label{exe:space_effic_occpos_lemma} Prove \Lemma{12.5} shown in \Sec{12.1.2}. 

\item Consider a generalization of Lempel--Ziv parsing where a phrase can point to its previous occurrence as a \emph{reverse complement}. Show that the space-efficient parsing algorithms of \Sec{12.1} can be generalized to this setting.
Can you modify also the bit-optimal variant to cope with reverse complements?

\item \label{exe:monotonicity} Prove the monotonicity of cost property for parse graphs described in \Sec{12.2}.

\item \label{exe:bitOptimal} Prove \Lemma{12.12} by contradiction, working on the shortest path $P = v_{x_1} v_{x_2} \dots v_{x_m}$ of the parse graph $G$ such that its first nonmaximal arc $(v_{x_i},v_{x_{i+1}})$ occurs as late as possible.

\item \label{exe:shortestPath} Prove \Thm{12.13}, using the algorithm for computing the single-source shortest path in a DAG described in \Sec{4.1.2}.

\item \label{exe:lengthMaximalArcs} Consider all arcs in the parse graph $G$ of \Def{12.10} that start from a given vertex, and let $b_{i_1}, b_{i_2}, \dots, b_{i_k}$ be a partition of such arcs into equivalence classes according to the number of bits required to encode their copy distances using encoder $f$. Describe an algorithm that, given the length of the distance-maximal arc of class $b_{i_p}$ and the length of the distance-maximal arc of the previous class $b_{i_{p-1}}$, where $p \in [2 \ltdots k]$, returns all the length-maximal arcs inside class $b_{i_p}$, in constant time per length-maximal arc.

\item \label{exe:maximalLCP} Recall from \Sec{12.2} the relationship between the length $\ell_e$ of a distance-maximal arc $e$ and the $\LCP$ of the suffixes of $S$ that start at those positions which are addressable with the number of bits used to encode the copy distance $d_e$ of arc $e$. Prove this property, using the definition of a distance-maximal arc.

\item \label{exe:buildingST} With reference to \Lemma{12.18}, show that sorting the set of suffixes $S'[h \ltdots |S|]\#$ with $h \in [p \ltdots q]$ coincides with computing the suffix array of string $W$.

\item \label{exe:buildingST2} Adapt \Lemma{12.18} to the case in which $\mathtt{source}$ and $\mathtt{target}$ do not intersect. \emph{Hint.} Sort the suffixes that start inside each of the two intervals separately, and merge the results using $\LCP$ queries.

\item \label{exe:prefixfree1} Describe how suffixes can be efficiently partitioned into extra, determined, and undetermined in the prefix-free parsing scheme for sorting the suffixes of a text.

\item \label{exe:prefixfree2} Give pseudocode for suffix sorting using prefix-free parsing. 

\item \label{exe:prefixfree3} Give pseudocode for run-length BWT construction using prefix-free parsing. 


\end{enumerate}

\end{document}  