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

\renewcommand{\thesubsection}{Problem \arabic{subsection}}
\newcommand{\Z}{\ensuremath{\mathbb Z}}

\begin{document}

\begin{center}
  {\Large\bf University of Waterloo}\\ \vspace{3mm}
  {\Large\bf CS240, Fall 2022}\\ \vspace{2mm}
  {\Large\bf Assignment 4}\\ \vspace{3mm}
  \textbf{Due Date: Wednesday, November 16, at 5pm}
\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
Please read \url{https://student.cs.uwaterloo.ca/~cs240/f22/assignments.phtml#guidelines} for guidelines on submission.
Submit your solutions electronically as \textbf{individual} PDF files with
names \texttt{a04q1.pdf}, \texttt{a04q2.pdf}, \texttt{a04q3.pdf} and \texttt{a04q4.pdf}, using MarkUs.
%Problem 5
%is a programming problem; submit your solution to 5 electronically
%as a file named .

\noindent
There are 49 possible marks plus 5 bonus marks available.
The assignment will be marked out of 49.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Hashing [3+3+3+3+2=14 marks]}
Consider a hash table dictionary with universe $U = \{0,1,2,\ldots,25\}$
and size $M=5$.  If items with keys $k=17,10,20,13$ are inserted in that order,
draw the resulting hash table if we resolve collisions using:
\begin{enumerate}
\part{a} Chaining with $h(k) = (k+3) \bmod 5$.
\part{b} Linear probing with $h(k) = (k+3) \bmod 5$
\part{c} Double hashing with $h_1(k) = (k+3) \bmod 5$ and $h_2(k) = 1 + 
(k \bmod 4)$.
\part{d} Cuckoo hashing with $h_1(k) = (k+3) \bmod 5$ and $h_2(k) = \left \lfloor
		  \frac{k}{5} \right \rfloor$.
\part{e} Identify a serious problem with the choice of hash functions
in part~(d).
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Quad Trees [6+3+3=12 marks]} 

\begin{enumerate} 
\part{a} One of the applications of quad trees is for \textbf{image compression}.
An image (picture) is recursively divided into quadrants
until the entire quadrant is only one colour.  Using this rule,
draw the quad tree of the following image. 
Use the convention that each
internal node of a quad tree has exactly four children, corresponding
to regions $R_{NE}$, $R_{NW}$, $R_{SW}$ and $R_{SE}$, in that order.
There are only three
colours (shades of grey).  For the leaves of the quad tree, use 1
to denote the lightest shade, 2 for the middle shade and 3 for the
darkest shade of grey. The bounding boxes in the internal nodes
do not need to be indicated.
\begin{center}
  \includegraphics[angle=90,width=3in]{grid}
\end{center}
\part{b} For an integer $k\geq 3$, consider a quad tree with bounding
box $[0,2^k) \times [0,2^k)$ storing four points
$\{(0,0),(2^{k-1}-1,2^{k-1}-1),(2^{k-1},2^{k-1}),(2^k-1,2^k-1)\}$.
Determine the height of the quadtree.
\part{c} For an integer $k\geq 3$, consider a quad tree with bounding
box $[0,2^k) \times [0,2^k)$ storing four points
$\{(0,0),(2^{k-1},2^{k-1}),(2^{k-1}+1,2^{k-1}+1),(2^k-1,2^k-1)\}$.
Determine the height of the quadtree.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Range Trees [5+5+5=15 marks]} 
\begin{enumerate}
\part{a} 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 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 nodes).
Provide the range counting query and justification of its runtime.
\part{b} Now consider the 2-dimensional-case: We have a set of $n$
2-dimensional points.  Given a query rectangle $R$, we want to find
the number of points that lie in $R$.  Preprocess the $n$ points
(by building an appropriate range-tree based data structure) such
that you can answer any of these counting queries in time $O((\log
n)^2)$.  Provide the range counting query and justification of its
runtime.
\part{c} Suppose a two dimensional range tree data structure stores
$n$ points, and that the $x$-BST is perfect, i.e., every level is
completely filled.  Derive an exact closed form formula, in terms
of $n$, for the sum of the number of nodes in the $x$-BST plus the
total number of nodes in all $y$-BSTs. 
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Covered Squares [8 marks]}
We are given a set $\mathcal W$ of $n$ square windows on the computer
screen $S$ (i.e., axis-parallel squares in the $(x,y)$-plane).  In
addition to a location on the screen, windows also have distinct
priorities.
If two windows overlap, then the window with greater priority
will cover the part of the window with lesser priority that it
overlaps with.

\begin{enumerate}
\part{a}
A new window is created with a priority that differs from all windows
in $\mathcal W$ and we wish to find all windows in $\mathcal W$
that are completely covered by the new window.  Give an algorithm
that finds all these windows in $O((\log n)^c + s)$ time, where $s$
is the number of windows that are found, and $c\geq 1$ is a constant.

Formally, each window is described via a 4-tuple $(x_{\ell},y_b,k,p)$ with
$(x_{\ell},y_b)$ the $(x,y)$-coordinate of the bottom left corner
of the window, $k$ the length of the sides of the window, and $p$ the
priority of the window.  If the new window is $W'=(x'_\ell,y_b',k',p')$,
your query should return in $O((\log n)^c + s )$ time all those windows
$W=(x_\ell,y_b,k,p)$ in $\mathcal W$ that are completely covered by the new
window.

To make this possible, you will need to assume that $\mathcal W$
is stored in a suitable data structure.  Describe what data structure you are
using.  This data structure should take at most $O(n(\log n)^c)$
space, and one should be able to build it in $O(n(\log n)^c)$ time.
\part{b} {\em 5 bonus marks:}  For part (a), a correct solution with $c$
any constant will earn full marks.  For 5 bonus marks, describe a solution
that has $c=4$.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}