\documentclass[12pt]{article}

\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools,algorithm,algorithmicx,algpseudocode, float, longtable}
\usetikzlibrary{shapes,positioning,calc,chains}
\usepackage[pdftitle={CS 240 Assignment 5},%
pdfsubject={University of Waterloo, CS 240,Spring 2022},%
pdfauthor={MP}]{hyperref}
\RequirePackage{pstricks,pst-node,pst-tree} % draw trees, requires using xetex
\newlength{\nodeLength}
\newcommand{\Node}{A}
\newcommand{\setnode}[1]{
	\settowidth{\nodeLength}{#1}
	\renewcommand{\Node}[1]{
		\Tcircle[name=#1]{\makebox[\nodeLength]{##1}}
	}
}
\setnode{99}


\newcommand{\alg}[1]{\ensuremath\mbox{\it #1}}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\renewcommand{\thesubsection}{Question \arabic{subsection}}

\newcounter{algorithmeligne}
\newcommand{\instr}[1]{%\underline
	{\bf #1}}
\newcommand{\nomproc}[1]{{\rm\bf #1}}
\newenvironment{algorithme}
{
	\setcounter{algorithmeligne}{0}
	
	\newcommand{\lign}{
		\stepcounter{algorithmeligne}
		{\footnotesize \arabic{algorithmeligne}.}\>
	}
	\begin{center}
		\begin{tabular}{|c|}
			\hline
			\begin{minipage}{1cm}
				\small
				\,
				\ \ \\[-11mm]
				\begin{tabbing}
					\hskip1cm\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\\\kill
				}
				{
				\end{tabbing}
				\ \ \\[-8mm]
			\end{minipage}
			\\\hline
		\end{tabular}
	\end{center}
}

% \snode{ID}{NUMBER} becomes \node{ID}[item]{\ensuremath{NUMBER}}
\newcommand{\snode}[2]{\node(#1)[item]{\ensuremath{#2}}}

% \nodelabel{SUBSCRIPT} becomes \node[label]{\ensuremath{S_SUBSCRIPT}}
\newcommand{\nodelabel}[1]{\node[label]{\ensuremath{S_#1}}}

\newcommand{\quesbox}[2]{\begin{center} \framebox[.5\textwidth]{%
			\raisebox{-5mm}[0mm][#1]{\begin{minipage}[t]{.45\textwidth}%
					{\normalsize\sf #2}{\phantom{ans}}\end{minipage}}} \end{center}}

\renewcommand{\thesubsection}{Problem \arabic{subsection}}
\definecolor{typo}{rgb}{0.75,0,0}
\definecolor{care}{rgb}{0,0,0}

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 Spring 2022}\\
\vspace{2mm}
{\Large\bf Assignment 5}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, July 20 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

The integrity of the grade you receive in this course is very important to you and the University of Waterloo.  
As part of every assessment in this course you must read and sign an Academic Integrity Declaration before you start working on the assessment and submit it \textbf{before the deadline of July 20th} along with your answers to the assignment; i.e. \textbf{read, sign and submit A05-AID.txt now or as soon as possible}.
The agreement will indicate what you must do to ensure the integrity of your grade.
If you are having difficulties with the assignment, course staff are there to help (provided it isn't last minute). \\
~\\
\textbf{The Academic Integrity Declaration must be signed and submitted on time or the
	assessment will not be marked.} \\
~\\
Please read
\url{https://student.cs.uwaterloo.ca/~cs240/s22/assignments.phtml#guidelines} for guidelines on submission.  
\textbf{Each question must be submitted individually to MarkUs as a PDF} with the corresponding file names: 
a5q1.pdf, a5q2.pdf, a5q3.pdf, a5q4.pdf, a5q5.pdf and a5q6.pdf. 
It is a good idea to submit questions as you go so you aren't trying to create several PDF files at the last minute. \\
~\\
\textbf{Late Policy:} Assignments are due at 5:00pm on Wednesday.  Students are allowed to submit \textbf{one} late assignment, 2 days after the due date on Friday by 5:00pm.  
Assignments submitted after Friday at 5:00pm or Wednesday at 5:00pm (if you have already used your one late submission) will not be accepted for grading but may be reviewed (by request) for feedback purposes only. If you want to use your one time late assignment allowance, please send an email to ``cs240@uwaterloo.ca'' with the title ``Using one time late assignment allowance''.\\  
%Note: you may assume all logarithms are base 2 logarithms:  $\log = \log_2$.

%%% Problem 1

\subsection{Max-$x$ in kd-trees [5 marks]}
Give an algorithm to find the point with the maximum $x$-value in a 2D kd-tree, and analyze its
complexity. For maximum credit, your algorithm must run in $o(n)$ time, where $n$ is the
number of points in the kd-tree. For simplicity, you may assume that $n$ is a power of $4$.
If the run-time $T (n)$ of your algorithm satisfies a recurrence relation that has already
been seen in class, you can take for granted the corresponding growth rate for $T (n)$, without
giving the proof.

%{\color{blue} Solution:
%		
%}
%
%{\color{red}\begin{longtable}{| c|p{13cm} |}
%		\hline 
%		+1 & mark for the correct formula \\ \hline
%		+2 & marks for explaining how the formula was derived \\ \hline
%		+2 & marks for working out the formula to the correct asymptotic running time \\ \hline
%	\end{longtable}
%}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Problem 2
\subsection{Huffman Coding [2+3 = 5  marks]}
\begin{itemize}
	\part{a} Trace the algorithm to build the Huffman trie for the string {\tt mississauga}, and name the result $T_1$. Repeat the process for the string {\tt massasauga}, and name the result $T_2$. 
	
	To break ties for tries of the same frequency, make the trie whose characters have a smaller ASCII sum the left child of the new root (that is, make it follow the ``0" label).
	
	
	\part{b} Compare the compression rates of the tries from part (a) for encoding the string {\tt massasagua}.
	
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Problem 3
\subsection{Run-Length Encoding [2+1+3+2 = 8  marks]}
Suppose we want to encode a ternary string, where each symbol is 0, 1, or 2, to a ternary string using RLE.
\begin{itemize}
	
	\part{a} What do you need to change in the RLE from the slides to make it work for a ternary string?
	
	\part{b} What are your ideas for making sure you are optimizing the compression rate?
	
	\part{c}  Present your algorithm as a pseudocode. 
	
	\part{d} What is the compression rate of your encoding scheme for the following ternary string?
	\[01200112200011122200001111222200000000000000111111111111111122222222222222222.\]
	
\end{itemize}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Problem 4



\subsection{Range Trees [3+4+4=11 marks]}
\begin{itemize}
	\part{a} Draw a 2-dimensional range tree of minimal height for the following set of average assignment and midterm grades:
	\begin{center}
		$\{(81, 70), (85, 68), (88, 88), (94, 68.5), (97, 75.5), (97.5, 100), (100, 80)\}$ 
	\end{center}
	
	\part{b} Assume that we have a set of $n$ numbers (not necessarily integers) and we are interested only
	in the number of points that lie in a range rather than in reporting all of them. Describe how a
	1-dimensional range tree (i.e., a balanced BST) can be modified such that a range counting query can be
	performed in $O(\log n)$ time (independent of $s$).  Briefly justify that your algorithm is within the expected run-time.
	
	\part{c} Next, consider the 2-dimensional case where we have a set of $n$ 2-dimensional points.
	Given a query rectangle $R$, we only want to find the number of points inside $R$, not the points themselves.
	Explain how to modify the Range Tree data structure discussed in class such that you can answer any of these
	counting queries in $O((\log n)^2))$ time.  Briefly justify that your algorithm is within the expected run-time.
	
\end{itemize}


\subsection{KMP [3+4=7 marks]}
%%% Problem 5
\begin{itemize}
	\part{a} Compute the failure array for the pattern $P=$\texttt{ississi}.
	
	\part{b}
	Show how to search for pattern 
	\begin{center} 
		$P=$\texttt{ississi} 
	\end{center}
in the text
\begin{center}
	$T=$\texttt{mississaugasmismississippimill}
\end{center}
 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 style in the example on slide~16 in Module~9.
	\begin{itemize}
		\item Place each character of $P$ in the column of the compared-to character of $T$.  
		\item Put brackets around the character if an actual comparison was not performed.
		\item Use a new row when sliding the pattern.
		\item You may not need all space in the table.
	\end{itemize}
	
\end{itemize}
\begin{table}
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
				\hline
				m&i&s&s&i&s&s&a&u&g&a&m&i&s&m&i&s&s&i&s&s&i&p&p&i&m&i&l&l\\
				\hline
				\hline
				&&&&&&&&&&&&&&&&&&&&&&&&&&&&\\
				\hline
				&&&&&&&&&&&&&&&&&&&&&&&&&&&&\\
				\hline
				&&&&&&&&&&&&&&&&&&&&&&&&&&&&\\
				\hline
				&&&&&&&&&&&&&&&&&&&&&&&&&&&&\\
				\hline
				&&&&&&&&&&&&&&&&&&&&&&&&&&&&\\
				\hline
				&&&&&&&&&&&&&&&&&&&&&&&&&&&&\\
				\hline
				&&&&&&&&&&&&&&&&&&&&&&&&&&&&\\
				\hline
				&&&&&&&&&&&&&&&&&&&&&&&&&&&&\\
				\hline
				&&&&&&&&&&&&&&&&&&&&&&&&&&&&\\
				\hline
				&&&&&&&&&&&&&&&&&&&&&&&&&&&&\\
				\hline
				%\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\
			\end{tabular}
	\end{center}
	\caption{Table for KMP problem (you may need to add rows, or delete some).}\label{kmp}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Problem 6

\subsection{Boyer-Moore [1+3+3+3+5=15 marks]}
\begin{itemize}
	\part{a} Construct the last occurrence function $L$ for pattern $P=ramammam$ 
	where $\Sigma = {a,k,m,r}$.
	
	\begin{tabular}{|c|c|c|c|c|} \hline
		c &  a &  k &  m &  r  \\ \hline
		L(c)&  &  &  &   \\ \hline
	\end{tabular}
%	
%	\begin{tabular}{|c|c|c|c|c|c|c|c|c|} \hline
%		i &  0 &  1 &  2 &  3 & 4 & 5 & 6 & 7 \\ \hline
%		P[i] & r & a & m & a & m & m & a & m \\ \hline
%		S[i] &  &  &  &  &  &  &  &  \\ \hline
%	\end{tabular}
	
	\part{b} Trace the search for $P$ in $T=ramaamamkmamramammam$ using the Boyer-Moore algorithm.
	Indicate in a table such as Table \ref{bmtable} which characters of $P$ were compared with which characters of $T$.
	Follow the example on slides 23-24 in Module 9.
	\begin{itemize}
		\item Place each character of $P$ in the column of the compared-to character of $T$. 
		\item Put brackets around the character if they are known to match from the previous step (similar to the examples in the slides). 
		\item Use a new row when sliding the pattern.
		\item  You may not need all space in the table.
	\end{itemize}
	\begin{table}[h]
		\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
					r&a&m&a&a&m&a&m&k&m&a&m&r&a&m&a&m&m&a&m\\
					\hline
					\hline
					&&&&&&&&&&&&&&&&&&&\\
					\hline
					&&&&&&&&&&&&&&&&&&&\\
					\hline
					&&&&&&&&&&&&&&&&&&&\\
					\hline
					&&&&&&&&&&&&&&&&&&&\\
					\hline
					&&&&&&&&&&&&&&&&&&&\\
					\hline
					&&&&&&&&&&&&&&&&&&&\\
					\hline
					&&&&&&&&&&&&&&&&&&&\\
					\hline
					&&&&&&&&&&&&&&&&&&&\\
					\hline
					&&&&&&&&&&&&&&&&&&&\\
					\hline
				\end{tabular}
		\end{center}}
		\caption{Table for Boyer-Moore problem.}\label{bmtable}
	\end{table}
	
	\part{c}For any $m\geq 1$ and any $n\geq m$, give a pattern $P$ and a text $T$ such that the Boyer-Moore 
	algorithm looks at exactly $\Theta(n/m)$ characters.  Justify your answer.
	
	\part{d} For any $m\geq 1$ and any $n \geq m$ that is a multiple of $m$, give a pattern $P$ and a text $T$
	such that the Boyer-Moore algorithm looks at all characters of the text at least once and returns with failure.
	Justify your answer.
	
	\part{e} A number of heuristics can be used with Boyer-Moore to reduce the number of comparisons performed
	between $P$ and $T$.  Suppose we use Boyer-Moore with only the Peek heuristic.  The Peek heuristic states
	that if $P[j] \neq T[i]$ and $P[j-1] \neq T[i-1]$ then the next location to search for $P$ at is $T[i+m-1]$.
	Show that the Peek heuristic may fail to find $P$ in $T$, i.e., find a pattern $P$, and a text $T$ containing $P$,
	such that Peek fails to find $P$ in $T$. Justify your answer in a short paragraph.
	
\end{itemize}


\end{document}
