\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{tikz} % this package is used for drawings
\usetikzlibrary{automata,arrows,shapes,decorations.pathreplacing} % we give some instructions to tikz

%%%%%%%%%% macros %%%%%%%%%%
  \newcommand\BXOR{\oplus}
  \newcommand\BOR{\mathbin{\mathtt{|}}}
  \newcommand\BAND{\mathbin{\mathtt{\&}}}
  \newcommand\BNOT{\mathbin{\sim}}
  \newcommand\BPLUS{\mathbin{+}}
  \newcommand\BLSHIFT{\mathbin{\mathtt{<<}}}
  \newcommand\BRSHIFT{\mathbin{\mathtt{>>}}}
  
  \newcommand{\Fig}[1]{Figure~\ref{#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 2. Algorithm design}

\begin{enumerate}[label=2.\arabic*]
\item \label{exe:fail}
Consider the $\mathtt{fail}(\cdot)$ function of the Morris--Pratt (MP) algorithm. We should devise a linear-time
algorithm to compute it on the pattern to conclude the linear-time exact pattern matching algorithm.
Show that one can modify the same MP algorithm so that on inputs $P=p_1 p_2 \cdots p_m$ and $T=p_2 p_3 \cdots p_m\#^m$, where $\#^m$ denotes a string of $m$ concatenated endmarkers $\#$,
the values $\mathtt{fail}(2)$, $\mathtt{fail}(3)$, \ldots, $\mathtt{fail}(m)$ can be stored on the fly before they need to be accessed.
\item \label{exe:KMP}
The Knuth--Morris--Pratt (KMP) algorithm is a variant of the MP algorithm with optimized $\mathtt{fail}(\cdot)$ function: $\mathtt{fail}(i)=i'$, where $i'$ is largest such that $p_1 p_2 \cdots p_{i'} = p_{i-i'+1} p_{i-i'+2} \cdots p_i$, $i'<i$, and $p_{i'+1}\neq p_{i+1}$. This last condition makes the difference from the original definition. Assume you have the $\mathtt{fail}(\cdot)$ function values computed with the original definition. Show how to update these values in linear time to satisfy the KMP optimization.
\item 
Generalize KMP for solving the \emph{multiple pattern matching} problem, where
one is given a set of patterns rather than only one as in the exact string matching problem. The goal is to scan $T$ in linear time so as to
find exact occurrences of any pattern in the given set. \emph{Hint.} Store the patterns in a tree structure, so that common prefixes of
patterns share the same subpath. Extend $\mathtt{fail}(\cdot)$ to the positions of the paths in the tree. Observe that unlike in KMP,
the running time of the approach depends on the alphabet size $\sigma$. Can you obtain scanning time $O(n \log \sigma)$?
Can you build the required tree data structure in $O(M \log \sigma)$ time, where $M$ is the total length of the patterns?
On top of the $O(n \log \sigma)$ time for scanning $T$, can you output all the occurrences of all patterns in linear time in the output size?
\item \label{exe:Hamiltonian1}
Show that a certificate for the Hamiltonian path problem can be checked in time $O(n)$ (where $n$ is the number of vertices) 
assuming an adjacency representation of the graph that uses $O(n^2)$ bits. \emph{Hint.} Use a table of $n$ integers that counts the number of occurrences of the vertices in the given certificate. 
\item \label{exe:Hamiltonian2} Suppose that we can afford to use no more than $O(m)$ space to represent the adjacency list. Show that
a certificate for the Hamiltonian path can now be checked in time $O(n\log n)$. 


\item \label{exe:bitparalleloperations}
Find out how bit-manipulation routines are implemented in your favorite programming language. We visualize below binary representations of integers with the most-significant bit first. You might find useful the following examples of these operations:
\begin{itemize}
\item \emph{left-shift}: $\mathtt{0000000000101001 \BLSHIFT 2 = 0000000010100100}$,
\item \emph{right-shift}: $\mathtt{0000000010100100 \BRSHIFT 5 = 0000000000000101}$,
\item \emph{logical or}: $\mathtt{0000000000101001 \BOR 1000001000001001 = 1000001000101001}$,
\item \emph{logical and}: $\mathtt{0000000000101001 \BAND 1000001000001001 = 0000000000001001}$,
\item \emph{exclusive or}: $\mathtt{0000000000101001 \BXOR 1000001000001001 = 1000001000100000}$,
\item \emph{complement}: $\BNOT \mathtt{0000000000101001=1111111111010110}$,
\item \emph{addition}: $\mathtt{0000000000101001 \BPLUS 0000000000100001 = 0000000001001010}$, and
\item  \emph{subtraction}: $\mathtt{0000000000101001 - 0000000000100001 = 000000000001000}$, \\ $\mathtt{000000000001000 - 000000000000001 = 000000000000111}$.
\end{itemize}
These examples use $16$-bit variables (note the overflow). Show two different ways to implement a function $\mathtt{mask}(B,d)$ that converts the $d$ most significant bits of a variable to zero. For example, $\mathtt{mask}(\mathtt{1000001000001001},7)=\mathtt{0000000000001001}$.
\item \label{exe:bitfieldarray}Implement with your favorite programming language a fixed-length bit-field array. For example, using C++ you can allocate with \[\texttt{A=new unsigned[(n*k)/w+1]}\]
an array occupying roughly $n \cdot k$ bits, where $w$ is the size of the computer word (unsigned variable) in bits and $k<w$. You should provide operations \texttt{setField(A,i,x)} and \texttt{x=getField(A,i)} to store and retrieve integer $x$ from $A$, for $x$ whose binary representation occupies at most $k$ bits.
\item \label{exe:treetoarray}Implement using the above fixed-length bit-field array an $O(n\log n)$-bit representation of a node-labeled static tree, supporting navigation from the root to the children.
\item Recall how stack, queue, and \emph{deque} work. Implement them using your favorite programming language using doubly-linked lists.

\item Given an undirected graph $G$, a subset $S \subseteq V(G)$ is called an \emph{independent set} if no edge exists between the vertices of $S$. In the independent-set problem we are given an undirected graph $G$ and an integer $k$ and are asked whether $G$ contains an independent set of size $k$. Show that the Independent set problem is NP-complete.

\begin{figure}[h!]
\centering
\begin{tikzpicture}[scale=1.4,-]
\draw[clip,draw=none] (-2,-3) rectangle (7,1.7);
\node[circle,draw=black,inner sep = -2mm,minimum size = 6mm,fill=white] (ax1) at (0,0) {$x_1$};
\node[circle,draw=black,inner sep = -2mm,minimum size = 6mm,fill=white] (ax2) at (0,-1) {$x_2$};
\node[circle,draw=black,inner sep = -2mm,minimum size = 6mm,fill=white] (ax3) at (0,-2) {$x_3$};
%
\node[circle,draw=black,inner sep = -2mm,minimum size = 6mm,fill=white] (bx1) at (1.5,1) {$x_1$};
\node[circle,draw=black,inner sep = -2mm,minimum size = 6mm,fill=white] (bnx2) at (2.5,1) {$\neg x_2$};
\node[circle,draw=black,inner sep = -2mm,minimum size = 6mm,fill=white] (bnx3) at (3.5,1) {$\neg x_3$};
%
\node[circle,draw=black,inner sep = -2mm,minimum size = 6mm,fill=white] (cnx1) at (5,0) {$\neg x_1$};
\node[circle,draw=black,inner sep = -2mm,minimum size = 6mm,fill=white] (cx2) at (5,-1) {$x_2$};
\node[circle,draw=black,inner sep = -2mm,minimum size = 6mm,fill=white] (cnx3) at (5,-2) {$\neg x_3$};
%
\draw[ultra thick] (ax1) to (bx1);\draw (ax1) to (bnx2);\draw (ax1) to (bnx3);\draw[ultra thick] (ax1) to (cx2);\draw (ax1) to (cnx3);
\draw (ax2) to (bx1);\draw (ax2) to (bnx3);\draw (ax2) to (cnx1);\draw (ax2) to (cx2);\draw (ax2) to (cnx3);
\draw (ax3) to (bx1);\draw (ax3) to (bnx2);\draw (ax3) to (cnx1);\draw (ax3) to (cx2);
\draw[ultra thick] (bx1) to (cx2);\draw (bx1) to (cnx3);
\draw (bnx2) to (cnx1);\draw (bnx2) to (cnx3);
\draw (bnx3) to (cnx1);\draw (bnx3) to (cx2);\draw (bnx3) to (cnx3);
%
\draw [-,decorate,decoration={brace,amplitude=5pt}] (-.25,-2.2) -- node[black,midway,xshift=-0.4cm] {$c_1$} (-.25,.2);
\draw [-,decorate,decoration={brace,amplitude=5pt}] (5.25,.2) -- node[black,midway,xshift=0.4cm] {$c_3$} (5.25,-2.2);
\draw [-,decorate,decoration={brace,amplitude=5pt}] (1.25,1.2) -- node[black,midway,yshift=0.4cm] {$c_2$} (3.75,1.2);
%
\node[draw=none,fill=none] (f) at (2.5,-2.5) {$f(x_1,x_2,x_3) = (x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee \neg x_2 \vee \neg x_3) \wedge (\neg x_1 \vee x_2 \vee \neg x_3)$};
%
\end{tikzpicture}
\caption{A reduction of the 3-SAT problem to the clique problem. A clique in $G_f$ is highlighted; this induces either one of the truth assignments $(x_1,x_2,x_3) = (1,1,0)$ or $(x_1,x_2,x_3) = (1,1,1)$. \label{fig:graphs-clique-reduction}}
\end{figure}

\item \label{ex:sat-clique}
A Boolean formula $f(x_1,\dots,x_n)$ is in \emph{3-CNF form} if it can be written as
\[f(x_1,\dots,x_n) = c_1 \wedge \cdots \wedge c_m,\]
where each $c_i$ is $y_{i,1} \vee y_{i,2} \vee y_{i,3}$, and each $y_{i,j}$ equals $x_k$ or $\neg x_k$, for some $k \in \{1,\dots,n\}$ (with $y_{i,1}$, $y_{i,2}$, $y_{i,3}$ all distinct). The subformulas $c_i$ are called \emph{clauses}, and the subformulas $y_{i,j}$ are called \emph{literals}. The following problem, called 3-SAT, is known to be NP-complete. Given a Boolean formula $f(x_1,\dots,x_n)$ in 3-CNF form, decide whether there exist $\alpha_1,\dots,\alpha_n \in \{0,1\}$ such that $f(\alpha_1,\dots,\alpha_n)$ is true (such values $\alpha_i$ are called a \emph{satisfying truth assignment}). 

Consider as ``new'' problem the clique problem from Example 2.3. Show that clique is NP-complete by constructing a reduction from 3-SAT. \emph{Hint.}~Given a 3-CNF Boolean formula
\[f(x_1,\dots,x_n) = (y_{1,1} \vee y_{1,2} \vee y_{1,3}) \wedge \cdots \wedge (y_{m,1} \vee y_{m,2} \vee y_{m,3}),\] construct the graph $G_f$ as follows (see \Fig{fig:graphs-clique-reduction} for an example):

\begin{itemize}
\item for every $y_{i,j}$, $i \in \{1,\dots,m\}$, $j \in \{1,2,3\}$, add a vertex $y_{i,j}$ to $G_f$;
\item for every $y_{i_1,j}$ and $y_{i_2,k}$ with $i_1 \neq i_2$ and $y_{i_1,j} \neq \neg y_{i_1,k}$, add the edge $(y_{i_1,j},y_{i_2,k})$.
\end{itemize}

Show that $f$ has a satisfying assignment if and only if $G_f$ has a clique of size $m$. 

\section*{Additional exercises not in the book}

\item \label{ex:clique-sat}
In Exercise~\ref{ex:sat-clique} above we have reduced the ``old'' problem 3-SAT to the ``new'' problem clique. Devise an opposite reduction, that is, show that the clique problem can be reduced in polynomial time to the 3-SAT problem. \emph{Hint.} Suppose we are given a graph $G$ on $n$ vertices $v_1,\dots,v_n$, and we are asked whether $G$ contains a clique with $k$ vertices. For every vertex $v_i$ and for every $j \in \{1,\dots,k\}$, introduce a Boolean variable $x_{i,j}$ with the meaning ``vertex $v_i$ is the $j$th vertex of the clique of size $k$''. What is the corresponding Boolean formula on the variables $x_{i,j}$?

\end{enumerate}

\end{document}  
