\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\calI{\ensuremath{\mathcal{I}}}
\def\part#1{\item[\bf #1)]}
\usepackage{tikz}
\usetikzlibrary{patterns,calc,chains,shapes.multipart,arrows,positioning,shapes,automata,fit,shadows,arrows.meta,trees}

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240E, Winter 2022}\\
\vspace{3mm}
{\Large\bf Assignment 2}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, February 2, 2022 at 5pm}
\end{center}

Be sure to read the assignment guidelines 
(\url{http://www.student.cs.uwaterloo.ca/~cs240e/w22/guidelines/guidelines.pdf}).
Submit your solutions electronically with individal PDF files named
a2q1.pdf, a2q2.pdf, \dots  (one per question).   

\medskip
\noindent{\bf Two policies specifically for Assignment 2:}
For some questions you may find helper-routines from predecessor-courses helpful.  
If the helper-routine is in the course notes (even if we have not gone over it), you
may use it without giving details.

Also, for this assignment you {\bf cannot compute
logarithms or exponentiations in constant time}; you need to compute
these from scratch as you need them.

\def\alg#1{\text{\it #1}}
\renewcommand{\thesubsection}{Question \arabic{subsection}}

\addtocounter{subsection}{-1}
\subsection{Academic Integrity Declaration}

Read, sign and submit {\tt A02-AID.txt} now or as soon as possible. 

\subsection{[6 marks]}

Let $A[0..n{-}1]$ be an unsorted array that stores integers, where each
entry is in the range $[0,n^5)$.    Entries in $A$ are not necessarily unique.
Design an algorithm to test whether there are indices $i$ and $j$ such that $|A[i]-A[j]|=10$.
The worst-case run-time and the auxiliary space must be in $O(n)$.

\noindent Remark: You are {\em not} allowed to use hashing for this question.  We have not even covered hashing
yet, but even if we had, its worst-case run-time is {\bf not fast enough}. 

\subsection{[5+3=8 marks]}
\begin{enumerate}
\part{a} 
Assume that you are given a non-empty list $L$ that contains $n$ key-value pairs
in sorted order, where $n+1$ is a Fibonacci-number.  Design an algorithm to build an 
AVL-tree that contains the key-value pairs from $L$ and has the maximum
possible height. (In other words: build a Fibonacci-tree containing the
items of $L$.)  The run-time 
and the auxiliary space must be $O(n)$.
\part{b} Prof.~Quirky thinks that he can do the above with a 
comparison-based algorithm even if list $L$ is in unsorted
order.  Show that this is not possible.
\end{enumerate}

\subsection{[4+1+6+6(+5)=17(+5) marks]}
Consider the following realization (called {\em buckets of sorted arrays})
    of ADT Dictionary.  We have an array $B[0\dots N{-}1]$ for some $N\geq 0$.
    Entry $B[j]$ is either NIL, or it stores an  array of size exactly $2^j$,
    with items in sorted order.    The following is an example.

\begin{center}
\begin{tikzpicture}[scale=0.8,line width=1pt,
                    start chain=going below,node distance=-1pt,
                    every node/.style={draw,minimum width=5mm,minimum height=5mm},
                    chainnode/.style={draw,minimum width=1.3cm,minimum height=8mm},
                    every label/.style={draw=none,minimum width=0pt,text=blue,font=\tt\footnotesize},
                    label distance=0mm]
%%%%%%%%% 0 %%%%%%%%%%%%%
  \node[on chain,chainnode, label={left:0},label={above:$B$}] (zero) {$\bullet$};
%\node[draw=none,above=1pt of zero] {$B$};
    \node[right=1cm of zero,rectangle] {45} edge[<-] (zero.center);
%%%%%%%%% 1 %%%%%%%%%%%%%
  \node[on chain,chainnode, label={left:1}] (one) {$\bullet$};
    \node[right=1cm of one,rectangle, rectangle split,rectangle split parts=2,rectangle split horizontal] {13 \nodepart{second} 60} edge[<-] (one.center);
%%%%%%%%% 2 %%%%%%%%%%%%%
  \node[on chain,chainnode, label={left:2}] (two) {NIL};
%%%%%%%%% 3 %%%%%%%%%%%%%
  \node[on chain,chainnode, label={left:3}] (three) {$\bullet$};
    \node[right=1cm of three,rectangle, rectangle split,rectangle split parts=8,rectangle split horizontal] {10 \nodepart{second} 17 \nodepart{third} 24 \nodepart{four} 31 \nodepart{five} 42 \nodepart{six} 49 \nodepart{seven} 55 \nodepart{eight} 56 } edge[<-] (three.center);
%%%%%%%%% 4 %%%%%%%%%%%%%
  \node[on chain,chainnode, label={left:4}] (four) {NIL};
%%%%%%%%% 5 %%%%%%%%%%%%%
    \node[on chain,chainnode, label={left:5}] (five) {NIL};
\node[left=2cm of zero,label={above:$n$}] {11};
\node[left=2cm of two,label={above:$N$}] {6};
\end{tikzpicture}
\end{center}

    \begin{enumerate}
    \part{a} Design an algorithm that does \alg{search}($k$) in buckets of sorted arrays in $O(\log^2 n)$ time.
        You may assume that you know $n$ and $N$, but $N$ could be arbitrarily large relative to $n$.
	You need not argue correctness, but explain your idea well.  Recall: For this assignment you can {\bf not} compute 
	$\log ()$ in constant time.
    \part{b} Insert key 40 into the example and show the resulting $B$.
        There are multiple possible answers; show
        the one that moves as few items as possible into a different bucket.
    \part{c} Design an algorithm to do \alg{insert}($k,v$)
	in such a way that as few items as possible are moved.  
	Your algorithm must have worst-case run-time $O(1+s)$,
	where $s$ is the number of items that were moved.
	You need not argue correctness.  
        You may assume that $N$ is sufficiently big so that the new item will fit.
    \part{d} 
        Define $\Phi := \sum_{j=0}^N \sum_{x\in B[j]} (N-j)$.    Briefly verify
    that this is a potential function, and then show that with this
        potential function (and a suitable choice of time units), the amortized time of \alg{insert} is $O(\log n)$.
    For this part you may assume that $N\in O(\log n)$.
    \part{e} {\bf (Bonus)} Design a version of \alg{insert}($k,v$) that does {\em not} assume that
        $N$ is sufficiently big (i.e., if needed, it increases the capacity of $B$ and copies 
        over if needed).  Argue that the amortized run-time for \alg{insert} is still $O(\log n)$.
	Clearly state what your potential function is (finding it is part of the problem),
	and by how much you increase the capacity of $B$ when copying over.  

	While a correct answer to e) likely contains correct answers to c) and d), for 
	ease of grading please write separate answers to c) and d) and refer to them in here
	as needed.
	\end{enumerate}

\subsection{[4+2+5+3+4=18 marks]}
Motivation:  Scapegoat trees as defined in class
store at each node $v$ the size of the subtree rooted at $v$.  This is not 
actually required; this assignment will guide you towards a variation that  operates without 
storing the size of the subtree.

\medskip
\noindent Define a {\em light scapegoat tree} to be a binary search tree  $T$
that is {\em height-balanced}, i.e.,
$$\alg{height}(T) \leq \lfloor \log_{4/3} n \rfloor.$$
You may assume that a light scapegoat tree knows its size $n$.
It does not store its height, and its nodes 
know neither the size nor the height of their subtrees.
You may assume that nodes have parent-references (the parent of the root is NIL).

Consider the following (incomplete) code to insert in such a tree:

\begin{algorithm}
\caption{\alg{LightScapegoatTree::insert}($k,v$)}
\tcp{Current tree is height-balanced}
$z\leftarrow \alg{BST::insert}(k,v)$\;
\If{\alg{notHeightBalanced}($z$)}{
     $p\leftarrow \alg{lowestSmallAncestor}(z)$\;
     completely rebuild the subtree at $p$ as a perfectly balanced subtree\
}
\end{algorithm}

\begin{enumerate}
\part{a}   Design algorithm \alg{notHeightBalanced}($z$).  This must achieve
    the following:  
    you are given a newly inserted node $z$ that is a leaf, and you must determine
    whether the current binary search tree is still height-balanced.  The run-time
    must be $O(\log n)$.    Recall: For this assignment you can {\bf not}
    compute $\log()$ in constant time. 
\part{b} 
    Show that if the tree is not height-balanced after \alg{BST::insert}, then
    there exists an ancestor $p$ of $z$ such that 
        $$\alg{size}(p) < \left( \tfrac{4}{3} \right)^{d(p,z)}.$$
    Here \alg{size}$(p)$ denotes the number of items in the subtree rooted at $p$.
    (We write this as a function, rather than as a field, to emphasize that
    this is {\em not} stored with the tree.)
    For any ancestor $v$ of $z$, $d(z,v)$ denotes the distance from $z$ to $v$, i.e., the
    number of levels that $v$ is above $z$. (So $d(z,z)=0$, $d(parent(z),z)=1$, etc.).
\part{c}  
    Design algorithm \alg{lowestSmallAncestor}($z$). This must achieve the
    following:  You are given
    the newly inserted node $z$, and you know that the tree is now not height-balanced.  You
    must find a node $p$ such that 
        $\alg{size}(p) < \left( \tfrac{4}{3} \right)^{d(p,z)}$.
    Furthermore, your $p$ must be the lowest ancestor of $z$ that satisfies this, i.e.,
    must minimize $d(p,z)$.  The run-time must be $O(\alg{size}(p)+\log n)$.

    Hint: Recall that you do {\em not} have the sizes of subtrees stored at each node.
    But in time $O(\alg{size}(p))$, you can compute the size of $p$.  How can you organize
    this so that over all ancestors of $z$ (until you have found the right one) you only
    spend time $O(\alg{size}(p))$?

\part{d} Let $p$ be the node returned by \alg{lowestSmallAncestor}.  Show that
after rebuilding the subtree at $p$ to be perfectly balanced, the resulting
binary search tree is height-balanced.
\part{e} Let $p$ be the node returned by \alg{lowestSmallAncestor}.  Show
    that  before rebuilding the subtree at $p$ we had
    $$|\alg{size}(p.\alg{left}) - \alg{size}(p.\alg{right})| \in \Omega(\alg{size}(p)).$$

\end{enumerate}


For all parts, you may use results of previous parts even if you did not prove them.
 

\medskip\noindent
Continuing the ``motivation'': We are {\em not} asking you do show that \alg{LightScapegoatTree::insert} has
$\Theta(\log n)$ amortized time, but it would be very easy to do so using the potential function
from class and taking into account part (e) as well as the run-times that you have achieved. 


\end{document}
