\documentclass[12pt]{article}
\usepackage{algo,fullpage,url,amssymb,epsfig,color,xspace,tikz,amsmath}
\usepackage{graphicx}
\usepackage[pdftitle={CS 240 Assignment 5},
pdfsubject={University of Waterloo, CS 240, Fall 2022},
pdfauthor={Arne Storjohann}]{hyperref}
\usepackage{algpseudocode,enumitem,calc,multicol}

\usepackage{listings}
\lstset{%
        language=C++,
        keepspaces=true,
        basicstyle=\small\ttfamily,
       commentstyle=\footnotesize\itshape{},
       identifierstyle=\slshape{},
       keywordstyle=\bfseries,
       numbers=left,
       numberstyle=\tiny{},
       numberblanklines=false,
       inputencoding={utf8},
       columns=fullflexible,
       basewidth=.5em,
        fontadjust=true,
        tabsize=3,
        emptylines=*1,
       breaklines,
       breakindent=30pt,
        prebreak=\smash{\raisebox{-.5ex}{\hbox{\tiny$\hookleftarrow$}}},
    escapeinside={//*}{\^^M} % Allow to set labels and the like in comments starting with //*
	}


\renewcommand{\thesubsection}{Problem \arabic{subsection}}

\begin{document}

\begin{center}
  {\Large\bf University of Waterloo}\\ \vspace{3mm}
  {\Large\bf CS240, Fall 2022}\\ \vspace{2mm}
  {\Large\bf Assignment 5}\\ \vspace{3mm}
  \textbf{Due Date: Wednesday, November 30, at 5:00pm}
\end{center}

\definecolor{care}{rgb}{0,0,0}
\def\question#1{\item[\bf #1.]}
\def\part#1{\item[\bf #1)]}
\newcommand{\pc}[1]{\mbox{\textbf{#1}}} % pseudocode

\noindent
Follow the guidelines for submission on the course webpage.\\

\noindent
There are 66 possible marks available.  
The assignment will be marked out of 66.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{KMP [6+6+6=18 marks]} 
\begin{enumerate}
\part{a} Compute the failure array for the pattern $P=\mathtt{bababx}$.
\part{b} Show how to search for pattern $P=\mathtt{bababx}$ in the
 text $T=\mathtt{baxbbabbabababxbaxbb}$ using the KMP algorithm.
Indicate in a table such as Table \ref{kmp} which characters of $P$
were compared with which characters of $T$. Follow the example on
Slide~11 of Module~9.  Place each character of $P$ in the column
of the compared-to character of $T$.  Put round brackets around 
characters if an actual comparison was not performed. You may need
to add extra rows to the table.
\part{c} Consider a pattern $P$ and a text $T$.  Assume that you
are given the failure array for the string $P\Phi T$: the concatenation
of $P$, a character $\Phi$ that is not contained in $P$, and $T$.
Explain how to use the failure array to find the
first occurrence of $P$ in $T$.
Note that you only have access to $P$ and the failure array for $P\Phi T$:
the text $T$ is not available.  
\end{enumerate}
\begin{table}[htbp]
	\Large{
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
 b&a&x&b&b&a&b&b&a&b&a&b&a&b&x&b&a&x&b&b\\
\hline
\hline
&&&&&&&&&&&&&&&&&&&\\
\hline
&&&&&&&&&&&&&&&&&&&\\
\hline
&&&&&&&&&&&&&&&&&&&\\
\hline
&&&&&&&&&&&&&&&&&&&\\
\hline
\end{tabular}
\end{center}}
\caption{Table for KMP problem.}\label{kmp}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\subsection{Boyer-Moore [3+7+5=15 marks]}
\begin{enumerate}
\part{a} Compute the last-occurrence function $L$ for the pattern 
 $P=\mathtt{abcbcbc}$.
Give your answer as a table as shown on Slide~18 of Module~9.  Note: 
$\Sigma = \{a,b,c\}$.
\part{b} Compute the suffix skip array $S$ for the pattern $P=\mathtt{abcbcbc}$.
Give your answer as a table as shown on Slide~19 of Module~9.
\part{c} Show how to search for pattern $P=\mathtt{abcbcbc}$ in the
text $T= \texttt{abcbaacbbabcbcbcbc}$ using the Boyer-Moore algorithm.
Indicate in a table such as Table~\ref{bm} which characters of $P$
were compared with which characters of $T$. Follow the example on
Slide~17 of Module~9.  Place each character of $P$ in the column
of the compared-to character of $T$.  Put round brackets around
characters which are known to be matched based on the suffix skip
array (even if the algorithm matches them again.) Put square brackets
around characters which are known to be matched based on the last
occurrence function (even if the algorithm matches them again.)  Note
that some lines in the table might require both square and round
brackets.  
\end{enumerate}
\begin{table}[htbp]
\Large{
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
a& b&  c&  b & a & a & c&  b & b & a & b & c & b & c & b & c&  b&  c \\

\hline
\hline
	&&&&&&&&&&&&&&&&&\\
\hline
	&&&&&&&&&&&&&&&&&\\
\hline
	&&&&&&&&&&&&&&&&&\\
\hline
	&&&&&&&&&&&&&&&&&\\
\hline
\end{tabular}
\end{center}}
\caption{Table for Boyer-Moore problem.}\label{bm}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Huffman Coding [5+2+6 = 13 marks]}
\begin{enumerate}
\part{a} \label{ex:huffman}
Construct the Huffman code for the following text $T=\mathtt{robots}$
over alphabet $\Sigma = \{\mathtt{b,o,r,s,t}\}$.

To make the answer to this part question unique, 
strictly follow these conventions for constructing the code:
To break ties, first use the smallest letter (according to
the alphabetical order), or the tree containing the smallest
alphabetical letter. When combining two trees of different
values, place the lower-valued tree on the left (corresponding
to a \texttt{0}-bit).  When combining trees of equal value,
place the one containing the smallest letter across both trees to the left.

The final code (a table with the codewords for all letters)
is sufficient for full marks.  You are highly encouraged,
though, to provide intermediate steps to get partial marks
in the presence of mistakes.

	\part{b} Use your Huffman code to decode the following bitstring:
	\[\texttt{10011110100}\]

	It is sufficient to list the final decoded string.

	(If you get stuck or obtain an unreadable sequence of letters
		you probably made a mistake in \hyperref[ex:huffman]{3(a)}.
		Make sure to fix it before moving on.)

	\part{c}
%Suppose $E$ is a function which gives a prefix-free code for an alphabet
%all prefix-free codes for $\Sigma$: $$ {\rm WPL}(E) := \sum_{c \in
%\Sigma} f(c)\, |E(c)| $$ Here, $|E(c)|$ denotes the length in bits
%of the code for $c$.  Note that ${\rm WPL}(E)$ is the
%length in bits of the encoding of $T$, not counting the space needed
%to store the dictionary.  Huffman's algorithm guarantees to produce
%a code that has minimal weighted path length.

For the alphabet $\Sigma$ and text $T$ from \hyperref[ex:huffman]{3(a)},
give an example of an optimal prefix-free code for $\Sigma$ that
can't be constructed by Huffman's algorithm, even if we don't specify
any conventions to break ties.  Explain why your example code can't
be constructed by Huffman's algorithm.

\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Suffix Trees [7+3+2+8 = 20 marks]} 
\begin{enumerate}
\part{a} \label{ex:suffix-tree}
Construct the suffix tree for $T = \mathtt{banana}$.
Use the end of word character \$. 
Children of a node should be ordered alphabetically, that is, the
labels on the edges are ordered alphabetically.  Note that \$ $< a$.
\part{b} \label{ex:repeat}
Define a \emph{repeat} in a string to be any pair of positions
$i\ne j$, so that there is an $\ell\ge 1$ with $T_{i,i+\ell-1}
= T_{j,j+\ell-1}$ i.\,e.\ two positions at which the same
substring of length $\ell$ is found.  We call $\ell$ the
length of the repeat at $(i,j)$ and $R = T_{i,i+\ell-1}$
the repeated pattern.

Find a repeated pattern $R$ of maximal length in the example
text $T = \mathtt{banana}$ and list its length and positions.
\part{c}
Traverse your suffix tree from \hyperref[ex:suffix-tree]{4(a)} along
your maximal repeated pattern $R$ from \hyperref[ex:repeat]{4(b)}
Where does the search stop; at a leaf, at an internal node
or inside an edge?  Mark the reached position in your suffix
tree in \hyperref[ex:suffix-tree]{4(a)}.
\part{d}
Let $T$ be a bitstring of length $n$.
Describe an algorithm that finds a repeated
pattern $R$ in $T$ of maximal length.  (Your algorithm does not
have to output the positions $(i,j)$.)

For full credit, your algorithm should have run time $O(n)$.
\end{enumerate}

\end{document}
