\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 4}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, March 22, 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 a4q1.pdf, a4q2.pdf, \dots  (one per question).

\subsection{[1+2+2+5=10 marks]} 
Assume we have a hash function $h$ for some table-size $M\geq 2$, and define a probe sequence as follows:
	\begin{align*}	
	h(k,0) & = h(k) \\
	h(k,i) & = h(k,i-1) + i \bmod M \quad \text{for $1\leq i<M$}
	\end{align*}
\begin{enumerate}[\bf a)]
\item Write the probe sequence for $h(k) = 0$ and $M=8$ starting from $i = 0$ to $i = M-1$.

\item Show that this probe sequence is an instance of quadratic probing.

\item Show that if $h(k,i){=}h(k,j)$ for some $0\leq i<j<M$, then $(j{-}i)(j{+}i{+}1) {=} 0 \bmod 2M$.

\item Assume that $M$ is a power of 2, say $M=2^m$ for some integer $m$.
Prove that all entries in the probe sequence are different, therefore the probe sequence will hit an empty slot.
\end{enumerate}

\subsection{[2+4+5 = 11  marks]} 

We have seen one method of obtaining a universal family of hash-functions
in class.  This assignment discusses another one.  Let us assume
that all keys come from some universe $\{0,\dots,U-1\}$, where $U=2^u$.
Therefore any key $k$ can be viewed as bitstring $x_k$ of length $u$ by
taking its base-2 representation.  

Let us assume further  that 
the hash-table-size $M$ is $M=2^m$ for some integer $m$, with $m<u$.
To choose a hash-function, we now randomly choose each entry in 
a $m\times u$-matrix $H$ to be 0 or 1 (equally likely). Then compute
$h_k = (H x_k) \% 2$, where $x_k$ is now viewed as a vector and
`\%2' is applied to each entry.
The output is a $m$-dimensional vector with entries in $\{0,1\}$; interpreting it as a length-$m$
bitstring gives a number $\{0,...,M-1\}$ that we use as hash-value $h(k)$.
For example, if $k=18$, $u=5$, $m=3$
and $H$ is as shown below, then $h(k)=1$ since
\begin{equation*}
\underbrace{\left( \begin{array}{ccccc}
0 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 & 0 
\end{array} \right)}_{H}
\underbrace{\left( \begin{array}{c} 1 \\ 0 \\ 0 \\ 1 \\ 0
\end{array} \right)}_{18 \text{ as length-5 bitstring}}
\hspace*{-3mm} \% 2
= 
\underbrace{\left( \begin{array}{c} 0 \\ 2 \\ 1 
\end{array} \right)}_{H x_k}
\% 2
= 
\underbrace{\left( \begin{array}{c} 0 \\ 0 \\ 1 
\end{array} \right)}_{1 \text{ as length-3 bitstring}}
\end{equation*}

\begin{enumerate}[\bf a)]
\item Let $H$ be the above matrix, $u=5$ and $m=3$.
	Consider the keys 9 and 13.  What are their hash-values 
	(as numbers in $\{0,\dots,M-1\}$?
	Show your work.

\item Consider again $u=5,m=3$ and keys $k=9$ and $k'=13$.
	Consider the same matrix $H$, except that
	the bits in the third column are randomly chosen.
	What is the probability that $h(k)=h(k')$?
	Justify your answer.

\item Assume now that all of $H$ is chosen randomly and independently.
	Show that (for any $u,m$) this 
	gives a universal hash function family,
	or in other words, $P(h(k)=h(k')) \leq \frac{1}{M}$
	for any two keys $k\neq k'$.

\item {[Possibly graded, 2 marks]} This method for obtaining universal hash-functions is much
less popular than using the Carter-Wegman functions.  Why do you
think that that might be the case?  (Expected length of answer
is 1-3 sentences.)
\end{enumerate}

\subsection{[1+2+9+5+4=21 marks]}

This assignment asks you to compare the performance of the MTF-heuristic
for binary search trees with splay trees.

\begin{enumerate}
\part{a}
\begin{minipage}[t]{0.8\linewidth}
Consider the binary search tree shown on the right.  
\begin{itemize}
\part{i}
What is its potential function value when viewed as a splay tree?
(State it with two fractional digits.)  
\part{ii}
Show the binary search tree that results if you perform \alg{splayTree::search}(50).
\end{itemize}

For both part-questions, it suffices to state the correct final answer
but we recommend showing some intermediate steps so we can give part-marks in case of errors.
\end{minipage}
\begin{minipage}[t]{0.1\linewidth}
\mbox{}
\scalebox{0.8}{%
\begin{tikzpicture}[level distance=29pt,
    every node/.style={circle,draw,minimum size=20pt},
    level 1/.style={sibling distance=64pt},
    level 2/.style={sibling distance=64pt},
    level 3/.style={sibling distance=32pt}]
	\useasboundingbox (-2,0) rectangle (5,-6);
    \node {70}
      child{node {20}
      	child{edge from parent[draw=none] }
        child{node{30}
      	  child{edge from parent[draw=none] }
          child{node {40}
      	    child{edge from parent[draw=none] }
            child{node {60}
              child{node {50}}
      	      child{edge from parent[draw=none] }
            }
	  }
        }
      }
      child{edge from parent[draw=none] }
    ;
\end{tikzpicture}
} % scalebox
\end{minipage}

\part{b} Let $T$ be a binary search tree with $n$ nodes and height $h=n-1$,
	i.e., $T$ is a path from the root to a unique leaf $x$.  Show that
	if we perform {\it splayTree::search}($k$) for the key $k$ at $x$,
	then the resulting tree $T'$ has height at most $h/2+c$ for some
	constant $c$.  Make $c$ as small as possible.  

	Hint: Show a bound on the height of the subtree rooted at $x$
	after you have done $i$ operations.

\part{c} Create an example of a binary search tree $T$ with $n$ nodes 
	and a sequence of $\Theta(n)$ operations {\it BST-MTF::search} 
	for keys in $T$ such that the total number of rotations
	is in $\Theta(n^2)$.

\part{d} Prof.~I.N.Correct claims that for any $n$ they have an example 
	of a binary search tree $T$ with $n$ nodes 
	and a sequence of $n$ operations {\it SplayTree::search} 
	for keys in $T$ such that the total number of rotations
	is in $\Theta(n^2)$.    In particular the actual run-time
	for these $n$ operations is in $\Omega(n^2)$.

	Prove that this is impossible.
\end{enumerate}

\subsection{[3 marks]}

Recall {\it interpolation-search}
(Algorithm 6.3 from the course notes) and consider its performance
for the sorted array $A[0..n{-}1]$ 
where $A[i] = ai + b$ for $0 \leq i \leq n - 1$ 
(for some constants $a >0$ and $b$ that are arbitrary real numbers).
Show that then a search for a key $k$ always takes $O(1)$ time, 
regardless of whether key $k$ is in $A$ or not.

\subsection{[8 marks]}

This question concerns sorting a set of 
infinite-precision numbers $x_0,\dots,x_{n-1}$.
Specifically, each $x_i$ is in $[0,1)$ and written in base-2.  It is given to you
implicitly, via an accessor-function {\it get-decimal-place}$(i,d)$,
which returns the bit in the $d$th decimal place of $x_i$.
For example, if $x_i=0.001001...$ then 
{\it get-decimal-place}$(i,3)=1$
and {\it get-decimal-place}$(i,4)=0$.
 Function {\it get-decimal-place} takes $\Theta(1)$ time.

Describe an algorithm to sort these (implicitly given) numbers $x_0,\dots,x_{n-1}$
in $O(n\log n)$ expected time, assuming
the numbers $x_0,\dots,x_{n-1}$
have been randomly and uniformly chosen from the interval $[0,1)$.
You may also assume that all numbers are distinct.
Note that comparing $x_i$ and $x_j$ is {\em not} a constant-time
operation!
Your output should be the sorting-permutation $\pi$ (i.e., $x_{\pi(0)}< x_{\pi(1)}< 
\dots <  x_{\pi(n-1)}$). 

A high-level description is enough, no need for
pseudo-code, and the correctness can be extremely short.  (But do argue the
run-time carefully.)  

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

\end{document}
