\documentclass[12pt]{article} 

%%%%%%% a few packages
\usepackage{fullpage}
\usepackage[ruled,vlined,linesnumbered,titlenumbered]{algorithm2e}
\DontPrintSemicolon
\SetKwInOut{Input}{Input}
\SetKw{KwBreak}{break}
\usepackage{color}
\usepackage{hyperref} % for the URL
\usepackage{verbatim} % for comments, for version control
\usepackage{ifthen} % for version control
\usepackage{todonotes} 
\usepackage{amsmath}
\usepackage{qtree} 
\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}


%%%%%% for pst-tree, define a node that ALWAYS has the same width (here "99")
\newlength{\nodeLength}
\newcommand{\Node}{A}
\newcommand{\setnode}[1]{ \settowidth{\nodeLength}{#1}
  \renewcommand{\Node}[1]{ \Tcircle{\makebox[\nodeLength]{##1}} }
}
\setnode{99}

%%%%%%%%%%%%%%%%%%%%% algo.sty copied over %%%%%%%%%%%%%%%%%%%%%
\newcounter{algorithmeligne}
\newcommand{\instr}[1]{%\underline
                        {\bf #1}}
\newcommand{\nomproc}[1]{{\rm\bf #1}}
\newenvironment{algorithme} { \setcounter{algorithmeligne}{0}
        \newcommand{\lign}{\stepcounter{algorithmeligne}
                \>{\footnotesize \arabic{algorithmeligne}.}\> }
        \begin{center}
        \begin{tabular}{|c|}
        \hline
        \begin{minipage}{1cm} \small \, \ \ \\[-11mm] \begin{tabbing}
\=\hskip1cm\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\\\kill 
        }
        {
        \end{tabbing}
        \ \ \\[-8mm]
        \end{minipage}
        \\\hline
        \end{tabular}
        \end{center}
        }



\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240E, Spring 2025}\\
\vspace{3mm}
{\Large\bf Assignment 3}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, June 17, 2025 at 5pm}, with a grace period until 7:59pm.
\end{center}


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


\subsection{[20 marks]}


We define a variant of AVL trees called \emph{d-AVL trees} as follows. Let $d$ be a fixed constant.
If the height of a node $z$ is greater than $d$, then the usual height-balance property of AVL-trees
must be satisfied at $z$.
If the height of a node $z$ is at most $d$, then there is no balance-property that needs to be
satisfied.
Show that a $d$-AVL tree with $n$ nodes has height $O(log n)$.

 
\subsection{[20 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}
\part{a} 
Argue that any comparison-based algorithm for the Selection problem
on $n$ items must have $\Omega(n/4)$ worst-case time.  For partial credit,
argue it must have $\Omega(\log n)$ worst-case time.  The $4$ here is a hint.


\part{b}
Let $T$ be a scapegoat tree that stores $n$ items.
Design an algorithm that solves {\tt Selection}$(T,k)$ 
in $O(\log n)$ time.

\end{enumerate}
 

\newpage

\subsection{[20 marks]}

Consider the following algorithm to find the minimum in a binary search tree.  
	\begin{algorithm}
        \caption{{\it findMin}(root $r$)}
	\lIf{($r$ is NIL)}{\KwRet{``empty tree''}}
        \lWhile{$r$.\alg{leftChild} $!=$ NIL} { $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{[20 marks]}

Motivation:  Scapegoat trees as defined in class
store at each node $z$ the size of the subtree rooted at $z$.  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  
that is {\em height-balanced}, by which we mean that the height is at most
$\lfloor \log_{4/3} n \rfloor$ (or equivalently, every node has depth
at most $\lfloor \log_{4/3} n \rfloor$).
You may assume that a light scapegoat tree has a field \emph{size} with
its number of items.  However, a light scapegoat tree does not store its 
height, and a node knows \emph{nothing} except its key and left and right subtree.
(In particular it knows neither its depth, nor its parent, nor the size of its subtree, 
nor the height of its subtree.)

Algorithm~\ref{alg:lightScapegoatInsert} gives (incomplete) pseudo-code to insert in such a tree:

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

\begin{enumerate}
\part{a}   Show that (after inserting the new leaf $z$) the tree can be
	height-unbalanced only if the depth of $z$ is too big.

\part{b}   Design algorithm \alg{height-unbalanced}($z$) to test whether the
	tree is now no longer height-balanced.  The run-time must be $O(\log n)$,
	where $n$ is the current size of the tree.

\part{c} 
    Show that if the tree is not height-balanced after \alg{BST::insert}, then
    there exists an ancestor $x$ of leaf $z$ such that 
        $$\alg{size}(x) < \left( \tfrac{4}{3} \right)^{d(x,z)}.$$
    Here \alg{size}$(x)$ denotes the number of items in the subtree rooted at $x$,
    and $d(x,z)$ denotes the distance from $z$ to $x$, i.e., the
    number of levels that $x$ is above $z$. (So $d(z,z)=0$, $d(parent(z),z)=1$, etc.).

\part{d}  Sub-routine \alg{lowest-small-ancestor}($z$) does the
following:  Find an ancestor $x$ of $z$ with $\alg{size}(x) < \left( \tfrac{4}{3} \right)^{d(x,z)}$,
and among all those, return the one that minimizes $d(x,z)$.
You need {\bf not} say how to implement this (it is not easy to do efficiently). 

Argue that the rest of the insertion-routine is correct.   Thus, show that
after rebuilding the subtree (at the node $p$ returned by \alg{lowest-small-ancestor})
to be perfectly size-balanced, the resulting
binary search tree is height-balanced.


\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 to show that \alg{LightScapegoatTree::insert} has
$\Theta(\log n)$ amortized time, but with the above results it would be very easy to do so using the potential function from class.


\subsection{[20 marks]}

Splay trees are, as AVL and $(2,4)$ trees, binary search trees whose
stucture can change each time an element is inserted or removed.
%
They differ in that their structure is also changing when an
element is simply searched in them, in order to adapt the structure of
the tree to the frequency of the search queries for each element, a
bit like the {\tt Move to front} heuristic on lists.

Splay trees support the search, insertion and deletion operations, but
we consider here only the search.
%
The search is performed as in any binary search tree, but is always
followed by a splay: if the element is found it is splayed to the
root, otherwise the last element accessed is splayed to the root.

The splay operation is performed on a node $x$ through a sequence of
splay steps, each of which moves it closer to the root.
%
Each particular step reorganizes the tree differently depending on the
position of $x$ relative to its grand-parent, if it has one.
\begin{itemize}
\item If $x$ is the left child of the root, a zig step (described
  in Figure~\ref{fig:zig}) is performed, and if $x$ is the right
  child of the root, a zag step (symmetric from the zig step) is
  performed.
\item If $x$ is the left-most grand-child of its grand-parent, a
  zig-zig step is performed (described in Figure~\ref{fig:zigzig}),
  and similarly a zag-zag step is performed if $x$ is the right-most
  grand-child of its grand-parent.
\item if $x$ is the right child of the left child of its grand-parent,
  a zig-zag step is performed (described in Figure~\ref{fig:zigzag}),
  and similarly a zag-zig step is performed in the symmetric case where
  $x$ is the left child of the right child of its grand-parent.
\end{itemize}

\begin{figure}[h]
  \begin{minipage}[t]{.45\textwidth}
    \begin{center}
      \Tree [ .g [ .p A [ .x B C ] ] D ] $\rightarrow$ \Tree [ .x [ .p
      A B ] [ .g C D ] ]
    \end{center}
    \caption{
      \textbf{Zig-zag Step}: when $x$ is the right child of $p$ and $p$
      is the left child of $g$, $p$ becomes the new left child of $x$,
      $g$ the new right child of $x$, and the subtrees $A$, $B$, $C$,
      and $D$ of $x$, $p$, and $g$ are rearranged as necessary.
    }\label{fig:zigzag}
  \end{minipage}
  \hfill
  \begin{minipage}[t]{.45\textwidth}
    \begin{center}
      \Tree [ .g [ .p [ .x A B ] C ] D ] $\rightarrow$ \Tree [ .x A [
      .p B [ .g C D ] ] ]
    \end{center}
    \caption{
    \textbf{Zig-zig Step}: when x is the left child of $p$ and $p$ is
    the left child of $g$.
%
    $p$ becomes the new right child of $x$, $g$ becomes the new right
    child of $p$, and the subtrees $A$, $B$, $C$, and $D$ of $x$, $p$,
    and $g$ are rearranged as necessary.
%
    % The other zig-zig case is the mirror image of this, i.e. when
    % $x$ is the right child of $p$ and $p$ is the right child of $g$.
    }\label{fig:zigzig}
  \end{minipage}
  \begin{minipage}[t]{.45\textwidth}
  \vspace{.5cm}
    \begin{center}
      \Tree [ .p [ .x A B ] C ] $\rightarrow$ \Tree [ .x A [ .p B C ]
      ]
    \end{center}
    \caption{
      \textbf{Zig Step}: when $x$ does not have a grandparent, the tree
      is updated through a simple rotation on the edge between $x$ and
      it's parent $p$.
      % 
      Zig steps exist to deal with the parity issue and will be done
      only as the last step in a splay operation and only when $x$ has
      odd depth at the beginning of the operation.
    }\label{fig:zig}
\end{minipage}
\hfill

\end{figure}

\renewcommand{\labelenumi}{\textbf{\alph{enumi})}}

\begin{enumerate}
\item Consider the binary search tree given in
  Figure~\ref{fig:starttree}.
  % 
  Describe a sequence of search queries which would transform this
  tree into the tree in Figure~\ref{fig:exampleTree}.
\begin{figure}[h]
\begin{minipage}{.95\textwidth}
	\begin{minipage}[t]{.45\textwidth}
	$$
		\Tree 
		  [ .8 [ .7 [ .6 [ .5 [ .4 [ .3 [ .2 [ .1 $\emptyset$ $\emptyset$ ] $\emptyset$ ] $\emptyset$ ]  
			  $\emptyset$ ] $\emptyset$ ] $\emptyset$ ] $\emptyset$ ] $\emptyset$	]
	$$
	\caption{The initial binary search tree used in the first question.}
	\label{fig:starttree}
	\end{minipage}\centering
	\hfill
	\begin{minipage}[t]{.45\textwidth}
	  $$
	  \Tree [ .1 $\emptyset$ [ .2 $\emptyset$ [ .3 $\emptyset$ [ .4
	  $\emptyset$ [ .5 $\emptyset$ [ .6 $\emptyset$ [ .7 $\emptyset$ [ .8
	  $\emptyset$ $\emptyset$ ] ] ] ] ] ] ] ] $$
	\caption{The target binary search tree used in the first question.}
	\label{fig:exampleTree}
	\end{minipage}\centering
\end{minipage}
\end{figure}

  

\item Draw the state of the tree after each search of the following
  sequence of search queries: $$1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8$$


\item Give a static binary search tree of optimal height containing the
 same set of elements.


\item Does the splay tree perform better or worse than the static
  binary search tree in terms of comparisons, on the sequence of
  searches given?
  % 
  If better, give a sequence of $5$ searches on which this splay tree
  performs worse.  If worse, give a sequence of $5$ searches on which
  this splay tree performs better.

\end{enumerate}


\end{document}
