\documentclass[12pt]{article} 

%%%%%%% a few packages
\usepackage{fullpage}
\usepackage[ruled,vlined,linesnumbered,titlenumbered]{algorithm2e}
\DontPrintSemicolon
\SetKwInOut{Input}{Input}
\usepackage{color}
\usepackage{hyperref} % for the URL
\usepackage{verbatim} % for comments, for version control
\usepackage{ifthen} % for version control
\usepackage{todonotes} 
\usepackage{amsmath} 
\def\part#1{\item[\bf #1)]}
\usepackage{tikz}
\usetikzlibrary{patterns,calc,chains,shapes.multipart,arrows,positioning,shapes,automata,fit,shadows,arrows.meta,trees}

\usepackage{adjustbox}

% two commands that we need frequently
\def\calI{\ensuremath{\mathcal{I}}}
\def\alg#1{\text{\it #1}}

%%%% a few things that are needed for the data base, but mostly ignored here
\newenvironment{solution}
	{\ifthenelse{\isundefined{\showSolution}}
		{\expandafter\comment}{\color{blue}\hfill\break{\bf Solution Ideas}:}}
        {\ifthenelse{\isundefined{\showSolution}}%
		{\expandafter\endcomment}{}}
		
\newenvironment{authorship}{\expandafter\comment}{\expandafter\endcomment}
\newenvironment{usage}{\expandafter\comment}{\expandafter\endcomment}
		
\newenvironment{suggestedMarkingScheme}
	{\ifthenelse{\isundefined{\showMarking}}
		{\expandafter\comment}{\color{brown}\hfill\break{\bf Marking Ideas}:}}
        {\ifthenelse{\isundefined{\showMarking}}%
		{\expandafter\endcomment}{}}
		
%%%%%%%% version control
% \newcommand{\showSolution}{show them} % comment out this line if not wanted
	% i.e., if you'd like to see suggested solutions
% \newcommand{\showMarking}{show them} % comment out this line if not wanted
	% i.e., if you'd like to see suggested marking scheme

% override so that we can use sections for each question
\renewcommand{\thesubsection}{Question \arabic{subsection}}

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240E, Winter 2024}\\
\vspace{3mm}
{\Large\bf Assignment 5}\\
\vspace{3mm}
\textbf{Due Date: Thursday, {\color{red}April 4}, 2024, at 5pm}
\end{center}

Be sure to read the assignment guidelines 
(\url{http://www.student.cs.uwaterloo.ca/~cs240e/w24/assignments.phtml}).
Submit your solutions electronically as individual PDF files 
named a5q1.pdf, a5q2.pdf, \dots  (one per question).


\textbf{Grace period:} submissions made before 11:59PM on {\color{red}April 4},
will be accepted without penalty.
Please note that submissions made after 11:59PM
\textbf{will not be graded} and may only be reviewed for feedback.

\subsection{[3+2+2=7 marks]}

Fast Fourier Transform gives us a way to multiply two polynomials
of degree $O(n)$ in $O(n \log n)$ time
(assuming arithmetic operations take constant time).
This question explores some of the many problems
we can solve by phrasing them as a polynomial product.

\begin{itemize}
\part{a} Given two vectors $a = [a_1, \dots, a_n]$
and $b = [b_1, \dots, b_n]$, explain how to compute the dot product
of $a$ with every cyclic shift of $b$ in $O(n \log n)$.

For instance, when $n = 3$, we would like to compute:
\begin{align*}
[a_1, a_2, a_3] &\cdot [b_1, b_2, b_3], \\
[a_1, a_2, a_3] &\cdot [b_2, b_3, b_1], \text{ and} \\
[a_1, a_2, a_3] &\cdot [b_3, b_1, b_2].
\end{align*}

\part{b} We are given two \textit{cyclic strips}
$a = [a_1, \dots, a_n]$ and $b = [b_1, \dots, b_n]$
where every entry of each of $a, b$ is either zero
or one. 

\vspace{1em}
\begin{minipage}[t]{\linewidth}
\centering
\adjustbox{valign=t}{
    \includegraphics[scale=0.3]{q1b.png}
}\\
\vspace{0.5em}
Figure 1: example cyclic strips.
\end{minipage}
\vspace{1em}

Give an $O(n \log n)$ algorithm
to find the number of ways to stack 
them on top of each other so that no two 
\textit{one} (1) entries of both $a$ and $b$ are adjacent.

\part{c} We are given one cyclic strip $a = [a_1, \dots, a_n]$
 where every entry of $a$ is either zero or one. Give an algorithm to
 find the number of ways to stack $a$ on top of itself so that all entries match.
 As before, the runtime should be in $O(n \log n)$.

\end{itemize}


\subsection{[3+2+3+3=11 marks]}

Recall that we had two versions of the KMP failure function:      For $j<m-1$
	\begin{itemize}
	\item $F[j]$ is the length of the longest prefix of $P$ that is a suffix of $P[1..j]$, and
	\item $F^+[j]$ is the length $\ell$ of the longest prefix of $P$ that is a suffix of $P[1..j]$
		and where additionally $P[\ell]\neq P[j{+}1]$, or 0 if no such $\ell$ exists.
	\end{itemize}
This assignment asks you to explore the difference that using $F^+$ can make.

\begin{itemize}
\part{a} Show the Knuth-Morris-Pratt automaton for the pattern $P=aaabaac$ for $\Sigma=\{a,b,c\}$,
	once when using $F$ for the failure-arcs and once when using $F^+$.

\part{b} Consider the pattern $P=a^m$ for some integer $m$.   For $1\leq j\leq m-2$, 
where does the failure-arc from state $j$ lead to if we use $F$ and $F^+$, respectively?
Briefly justify your answer.

\part{c} Show that using $F^+$ can cut the number of checks in half.
	(Recall that a {\em check} is testing whether $P[j]=T[i]$ for some $j,i$, as done in line 5
	of \alg{KMP::patternMatching}).   


	To do so, design (for all sufficiently large $n$) a text $T$ of length $n$ and a pattern $P$ 
	that does not exist in $T$, but detecting this with KMP takes almost twice as many checks with $F$ than it
	does with $F^+$.   (You can choose the length of $P$; it suffices to give one $P$ for each $n$.)
	Justify your choice by arguing how many checks are taken with each failure-function.
	

	[``Almost twice as many'' means that as $n$ goes to infinity, the ratio between the number of checks
	should go to 2.]

\part{d} Show that for any text $T$ and any pattern $P$ not in $T$, using $F$ will require at most
twice as many checks as using $F^+$.   
\end{itemize}

\subsection{[2+4+7=13 marks]}

\begin{itemize}
	\part{a} Consider the text $S=${\tt ARECEDEDDEER}.    Show a Huffman-trie for this text
	(using $\Sigma_S=\{A,C,D,E,R\}$).   Also indicate with every node (including
	interior nodes) the frequency that this node had when building the Huffman-trie.
	
	\part{b} Assume we have characters $x_1,\dots,x_n$ where $x_i$ has frequency
	$F(i)$.  Here $F(i)$ is the {\em Fibonacci-sequence}: $F(1)=1, F(2)=1$,
	$F(i)=F(i{-}1)+F(i{-}2)$ for $i\geq 3$.
	Argue that any Huffman tree of these characters has height $n{-}1$. 
	
	{\bf Hint:} For $i\geq 2$, what is the frequency associated with the parent $p_i$ of $x_i$?

	\part{c} Assume we have characters $x_1,\dots,x_n$ where $x_i$ has
	frequency $f_i$ and $\min_i \{ f_i \} = 1$.
	Assume further that some Huffman-tree $T$ for these characters has height
	$n{-}1$.  Argue that $\max_i \{ f_i \} \geq F(n{-}1)$, where $F(\cdot)$ is again the Fibonacci-sequence.
	
	{\bf Hint:} Use the structure of a binary tree of height $n-1$ to
	enumerate your characters suitably, and then argue a lower bound on $f_i$
	and on the frequency associated with the parent $p_i$ of $x_i$.
\end{itemize}

\subsection{[2+4+2=8  marks]}

This question concerns Lempel-Ziv-Welch encoding of the word $A^n$, which is the
word consisting of $n$ copies of the character $A$.  In the
following, use as alphabet the 128 ASCII characters, stored with 
code-words 0 up to 127.  
In particular, `$A$' has code-word 65, and the first code-word you can use
for strings added to the dictionary is 128.

\begin{itemize}
\part{a} Give the encoding (as list of numbers, {\em not} as a
    bit-string) of $A^{16}$.  Show your work.

\part{b} Recall that traditional Lempel-Ziv-Welch converts integers into
	12-bit strings. This means that when we add codeword
	4096 to the dictionary, this would result in an overflow-error.  

	When encoding $A^n$, what is the smallest $n$ for which we get
	this overflow-error?  Justify your answer theoretically (i.e.,
	the answer ``I implemented LZW and it used code 4096 at $n=X$'' will
	{\em not} give you credit.)

\part{c} Let $X$ be the answer that you got in part (b).  Prove that
	for {\em any} ASCII-string of length $X$ or more, using 
	Lempel-Ziv-Welch leads to a dictionary-overflow.
\end{itemize}

\subsection{[2+2+3+3=10 marks]}

\newcommand{\concat}{\ensuremath{\!+\!\!\!\!+}}
    
Recall the Elias-Gamma codes from class; we use $E_\gamma(N)$ to denote it for integer $N\geq 1$.
\begin{itemize}
\part{a} Show the trie that stores $E_\gamma(N)$ for $N\in \{1,\dots,7\}$.

\part{b} Elias-Gamma codes begin with long runs of 0.
	For this reason, an idea to obtain shorter codes is to
	encode these runs recursively.   Specifically the {\em recursive Elias-Gamma code} $E_r(N)$ 
	is computed with Algorithm~\ref{alg:recursiveEliasGamma} given below.
	\begin{algorithm}
\caption{\alg{recursiveEliasGamma::encodeOneNumber}($N$)}
	\label{alg:recursiveEliasGamma}
	\tcp{pre: $N\geq 1$}
	$c\gets$ empty word\;
	\While{$N>1$} {
		$w\gets$ binary representation of $N$\;
		$c.\alg{prepend}(w)$\;
		$N\gets |w|-1$\;
	}
	$c.\alg{prepend}(0)$\;
	return($c$)
	\end{algorithm}	

	Show $E_r(N)$ and $E_\gamma(N)$ for $N=2,4,8,16$.  No explanation needed.

\part{c} You should notice that $|E_r(N)|\geq |E_\gamma(N)|$ for $i=1,\dots,16$.   What is the
	smallest value of $N$ such that $|E_r(N)|<|E_\gamma(N)|$?   Justify your answer.

\part{d} Consider the following bitstring: 
	$$C=0\,1\,1\,1\,0\,1\,0\,1\,0\,0\,1\,1\,0\,1\,0\,1\,0\,1\,0\,0\,1\,1\,0\,1\,0\,1\,0\,1 $$
which has the form $C=E_r(N_1)\concat E_r(N_2)\concat \dots \concat E_r(N_k)$ for some integer $k\geq 1$ and integers $N_1,\dots,N_k\geq 1$.
What is $N_1$?   Explain how you obtained the answer by describing the idea for an algorithm that would convert
any concatenation of recursive Elias-Gamma codes into the corresponding list of integers. Also show how this algorithm worked to obtain $N_1$.
(You do not have to give the details of the algorithm, or analyze its correctness or run-time.)
\end{itemize}



\end{document}
