\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\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 2024}\\
\vspace{3mm}
{\Large\bf Assignment 3}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, March 5, 2024, at 5pm}
\end{center}

Be sure to read the assignment guidelines 
(\url{https://student.cs.uwaterloo.ca/~cs240e/w24/assignments.phtml#guidelines}).
Submit your solutions electronically as individual PDF files 
named a3q1.pdf, a3q2.pdf, \dots  (one per question).

Ensure you have read, signed, and submitted the \textbf{Academic
Integrity Declaration} AID02.TXT.

\textbf{Grace period:} submissions made before 11:59PM on March 5,
will be accepted without penalty.
Please note that submissions made after 11:59PM
\textbf{will not be graded} and may only be reviewed for feedback.

\subsection{[6+6=12 marks]}

Consider the following algorithm to find the minimum in a binary search tree.  
        \begin{algorithm}
        \caption{{\it findMin}(root $r$)}
        \lIf{($r$ is null)}{\KwRet{``empty tree''}}
        \lWhile{$r$.\alg{leftChild} $!=$ null} { $r\gets r$.\alg{leftChild} }
        \KwRet{$r$.key}
  \end{algorithm}

        Let $T^{\rm avg}(n)$ (for $n\geq 0$) be the average-case number of executions of the while-loop in \emph{findMin} for a tree with $n$ nodes.  Here the average is taken over all binary search trees that store $\{0,\dots,n{-}1\}$, and $T^{\rm avg}(0)=T^{\rm avg}(1)=0$.

\begin{itemize}
\part{a} Show that for $n\geq 2$ we have $T^{\rm avg}(n)\leq 1 + \tfrac{1}{C(n)} \sum_{i=0}^{n-1}
        C(n{-}i{-}1)C(i) T^{\rm avg}(i)$, where $C(n)$ is the number of
        binary search trees that stores $\{0,\dots,n{-}1\}$.  Be as precise
        as we were in class for \alg{avgCaseDemo}.
\part{b} Show that $T^{\rm avg}(n)\in O(\log n)$.
        (We recommend that you show $T^{\rm avg}(n)\leq 2\log n$, and that you 
        consider a `good case' where the left subtree has size at most $n/2$.)
        You may use without proof that  $C(n)
                =\sum_{i=0}^{n-1} C(i)\cdot C(n{-}i{-}1)$,
        and you may assume that $n$ is divisible as needed.)
\end{itemize}


\subsection{[3+5=8 marks]}

Recall that the {\tt Selection} problem receives as input a
set of $n$ items and an integer $k$ with $0\leq k\leq n-1$ and it must return the
item that would be at $A[k]$ if the items were put into an array
$A$ in sorted order.


\begin{enumerate}
\item 
Argue that any comparison-based algorithm for the Selection problem
on $n$ keys must have $\Omega(\log n)$ worst-case time.

\item
Let $T$ be an scapegoat($\frac{2}{3}$)-tree that stores $n$ items.
Argue that {\tt Selection}$(T,k)$ can be done in $O(\log n)$ time.
\end{enumerate}

\subsection{[5 marks]}

Let $S$ be a skip list with $n\geq 4$ items.  Assume that the lists $S_0,S_1,\dots,S_h$ 
of $S$ have the following property for all $0\leq i<h$.  
\begin{quotation}
If $|S_i|=1$ then $|S_{i+1}|=0$.  If $|S_i|>1$, then $|S_{i+1}|\leq \sqrt{|S_i|}$.
\end{quotation}
What is the maximum possible value of $h$, relative to $n$?  For full marks, you should give
an exact bound (no asymptotics), make no assumptions on the divisibility of $n$, and show
that your bound is tight for infinitely many some values of $n$.
(But part-marks may be given otherwise.) Justify your answer.

\subsection{[3 marks]}

Let $A$ be an unordered array with $n$ distinct items $k_0,\dots,k_{n-1}$.
Give an asymptotically tight $\Theta$-bound on the expected access-cost
if you put $A$ in the optimal static order for the following probability 
distribution:

$$\text{$p_i = \frac{1}{(i+1) H_{n}}$ for $0 \leq i \leq n-1$ where
$H_{n} = \sum_{j=1}^n \frac{1}{j}$.}$$

For example, for $n=4$ we have $H_4=1+\tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{4}=\tfrac{25}{12}$ and the items would 
have access probabilities $\langle
\frac{12}{25},\frac{6}{25},\frac{4}{25},\frac{3}{25}\rangle$.


\subsection{[3+3+8=14 marks]}

\begin{itemize}
\part{a} In lecture, we only look at the key in a van Emde Boas tree. Give a way to efficiently manage values. 
Explain how to support the required operations (min, max, search, predessor, successor, insert, delete), and analyze
the space requirements.

\part{b} A vEBT uses $\Theta(u)$ space regardless of the number $n$ of items that are actually stored. We would like
to use less space and keep the worst-case time of $O(\log\log u)$ for each operation.
To do so, one could replace the array cluster by a structure
storing only the non-empty cluster.
Argue that a BST-based dictionnary is not an appropriate implementation.

\part{c} Propose an adapted vEBT structure that uses only $O(n)$ space and supports the operations in \textit{expected}
$O(\log\log u)$ time.
You should explain your changes, how they impact the vEBT operations, and the new operations you might need.
\end{itemize}

\end{document}
