\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 2023}\\
\vspace{3mm}
{\Large\bf Assignment 3}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, March 8, 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 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 8,
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{[8+10=18 marks]}

In an AVL-tree, a lot of time is spent during updates on doing rotations.
We can cut down on the number of rotations by allowing a larger imbalance.
Let a $k$-AVL-tree (for some integer $k\geq 1$)
be a binary search tree
where for every node, the difference of heights of its left and right subtree
is at most $k$.

\begin{enumerate}
\part{a} Show that any $k$-AVL-tree (for $k\geq 1$) has height at most 
$(k{+}1) \log (n{+}1)$.

\part{b} Improve the bound of part (a). 
	Thus, show that the height of a $k$-AVL-tree 
	is at most $c(k{+}1) \log (n{+}1)$ for some
	constant $c<1$.    How small can you make $c$?    You may
	assume constant lower bounds on $k$ as needed, e.g., $k\geq 2$.
	
	Part-marks will be given if you at least show that
	any $2$-AVL-tree has height at most $2 \log (n+1)$.

\end{enumerate}


\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$.


\end{document}
