\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,enumerate} 
\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}

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

% 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 2023}\\
\vspace{3mm}
{\Large\bf Assignment 5}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, April 5, 2023, at 5pm}
\end{center}

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

\subsection{[4+3+2+3=12 marks]}

Let $P$ be a set of $n$ points in general position.
A {\em 2-dimensional partial match query} specifies a value $a$,
and asks whether there are any points in $P$ that have either $x$-coordinate $a$
or $y$-coordinate $a$ (or both).
\begin{enumerate}[\bf a)]
\item Assume $P$ is stored in a 2-dimensional kd-tree.  Design an 
algorithm that can answer a partial match query in $O( \sqrt{n})$ time.  

\item Argue that any comparison-based algorithm to do
partial matches must use $\Omega(\log n)$ comparisons on some instance
of size $n$.

\item Assume $P$ is stored in a 2-dimensional range-tree.  Design an 
algorithm to answer a partial match query.  Make it as efficient as you
can.  It suffices to describe the idea and analyze the run-time.

\item Design a data structure to store $P$ that uses $O(n)$ space 
and permits to insert points, delete points, and answer
2-dimensional partial match queries in $O(\log n)$ worst-case time.   
Briefly say how these operations are implemented.
\end{enumerate}

\subsection{[5+5=10 marks]} 

A {\em range-counting-query} is like a range search, except that
you only need to report {\em how many} items fall into the range,
you do not need to list which items they are.
 
\begin{enumerate}[\bf a)]
\item Describe how any balanced binary search tree
can be modified such that a range counting query can be performed
in $O(\log{n})$ time (independent of $s$, the number of points in
the query-interval).
Briefly state the changes needed, then describe the algorithm 
for the range counting query. 

\item Now consider the 2-dimensional-case: Describe
an appropriate range-tree based data structure such
that you can answer range-counting-queries among
2-dimen\-sio\-nal points in time $O((\log n)^2)$.    Then
describe the algorithm for the range counting query. 
\end{enumerate}

\subsection{[7 marks]}

Let $T$ be a 01-string of length $n$. Describe an algorithm that 
has run-time $O(n)$ and finds
the longest pattern $P$ that occurs {\em at least twice} in $T$.

The two occurrences of $P$ may overlap each other (e.g. for
$T=011010100$, we have $P=1010$) and they need not be adjacent
(e.g. for $T=0111010111$ we have $P=0111$).  If there are multiple
such patterns $P$, then an arbitrary one should be returned.

\subsection{[3+3+3=9 marks]}

We are searching for pattern $P$ in text $T$
where $|T|=n$, $|P|=m$, and $n\geq m\geq 1$.

\begin{enumerate}[\bf a)]
\item Show that any pattern matching algorithm 
must look at at least $\lfloor n/m \rfloor$ characters of $T$
in the worst case.

\item Consider pattern $P=0^m$ and let text $T$ be a string of $n\geq m$ bits
that were randomly chosen to be 0 or 1 with equal probability.  
Let $X$ be the number of checks  done by Boyer-Moore until it
mismatches for the first time or returns with success. 
(The check that leads to a mismatch is included in this count.)
Show that $E[X]\leq 2$.

\item Consider the same setup as in the previous part.  Assume you
just had a mismatch.  Show that the expected amount by which you shift
the guess forward is at least $m-1$.
\end{enumerate}

Motivation:  For the 
special string $P=0^m$, 
the expected number of checks is hence $\approx 2\tfrac{n}{m-1}$
(i.e., roughly within a factor 2 of the lower bound)
because you expect to do 2 checks until a mismatch and then shift 
forward by $m-1$ characters.

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

\begin{enumerate}[\bf a)]
\item 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.

\item 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$?

\item 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{enumerate}

\end{document}
