\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 14. Haplotype analysis}

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

\item\label{genomics:exe-HA-NP-hard}
Complete the proof of \Thm{14.1}, by proving that, if $A$ and $B$ are two haplotypes obtained with $|V||E| - 2t$ bit flips from $M$, then the set $C = \{i \st A[2i-1] = A[2i] = 0\} \subseteq V$ has the property that there are $t$ edges between $C$ and $V \setminus C$. Obtain this proof by showing the following intermediary properties:
\begin{itemize}
\item $A[2i-1] = A[2i]$, for all $i \in \{1,\dots,|V|\}$;
\item $B[2i-1] = B[2i]$, for all $i \in \{1,\dots,|V|\}$;
\item $A$ is the bit-wise complement of $B$.
\end{itemize}

\item\label{exe:haplotypeassembly}
Show that the algorithm given for the haplotype assembly in the framework of the minimum error correction problem can be optimized to run in $O((2^K+r)s)$ time. How could you get the time complexity down to $O(2^Ks)$?

\item \label{exe:haplotypeassembly-memory} Show how the algorithm given for the haplotype assembly in the minimum error correction problem can be implemented to use $O(2^K\sqrt{s})$ memory, while maintaining the same asymptotic time complexity.
\emph{Hint:} Use the same idea as in \Exe{7.2}.

\item\label{exe:haplotypeassembly-error}
Let $T$ denote the maximum number of bit flips needed in any column of the matrix $M$ in an optimal solution to \Prob{prob:haplotypeassembly}. Show that the algorithm given for this problem can be modified to run in time $O((K^T+r)s)$, and even in time $O(K^Ts)$ (see also \Exe{14.2} above).

\item\label{exe:haplotypeassembly-weight}
Consider the problem of haplotype assembly under minimum error correction in which each cell of $M$ has also a cost of flipping, and one is looking for a partition of the rows of $M$ that is compatible with two haplotypes and minimizes the sum of the costs of all bit flips. What changes to the algorithm we presented are needed in order to solve this more general problem with the same time complexity?

\item 
Recall the definition of matching statistics from Section 11.3.3. We are interested in the related notion of \emph{positional matching statistics}: given an $m \times n$ haplotype matrix $P$ and a query haplotype sequence $S$ of length $n$, compute the array $\mathsf{pMS}_{S,P}[1..n]$ that stores at position $j$ the length of the longest suffix of $S[1..j]$ that equals $P[i..j]$ for some $i \leq j$. Describe how to compute $\mathsf{pMS}_{S,P}$ using the prefix and divergence arrays from Section 14.2.2. What is the time complexity of your algorithm?

\end{enumerate}

\end{document}  