\documentclass[12pt]{article} 

%%%%%%% a few packages (not all of which are necessarily needed)
\usepackage{fullpage}
\usepackage{amsmath,amssymb}
\usepackage{color}
\usepackage{hyperref} % for the URL
\usepackage[ruled,vlined,linesnumbered,titlenumbered]{algorithm2e}
\DontPrintSemicolon
\SetKwInOut{Input}{Input}
\SetKw{KwBreak}{break}
\usepackage{verbatim} % for comments, for version control
\usepackage{ifthen} % for version control
\usepackage{todonotes} 
\def\calI{\ensuremath{\mathcal{I}}}

%%%%%% other possibly useful things
\def\part#1{\item[\bf #1)]}
\renewcommand{\thesubsection}{Question \arabic{subsection}}
\newcommand{\alg}[1]{\text{\emph{#1}}}

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240E, Spring 2026}\\
\vspace{3mm}
{\Large\bf Written Assignment 2}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, June 9, 2026 at 5:00pm}\\
\end{center}

Be sure to read the assignment guideliness
(\url{https://student.cs.uwaterloo.ca/~cs240e/s25/assignments.phtml#guidelines}).
Submit your solutions electronically to Crowdmark. Ensure you have read, signed, and submitted the \textbf{Academic
Integrity Declaration} AID01.

\textbf{Grace period:} submissions made before 7:59pm on June 9 will be accepted without penalty. Please note that submissions made after 7:59pm
\textbf{will not be graded} and may only be reviewed for feedback.


\subsection{[1+1+7=9 marks]}

Let $T(w)$ be the number of times that we print a `*' when calling Algorithm~\ref{alg:silly-algo} with a bitstring $w$ of
length $n$.     Now let $T^{\rm best}(n)$, $T^{\rm worst}(n)$, and $T^{\rm avg}(n)$ be
the best, worst, and average of this (over all bitstrings of length $n$).

\bigskip
\hspace*{-5mm}
\begin{minipage}[t]{0.43\linewidth}
\begin{itemize}
\part{a} Prove an $O$-bound on $T^{\rm best}(n)$.
\part{b} Prove an $\Omega$-bound on $T^{\rm worst}(n)$.
\part{c} Show that $T^{\rm avg}(n)\in O(T^{\rm best}(n))$.
\end{itemize}
\end{minipage}
\hspace*{\fill}%
\begin{minipage}[t]{0.55\linewidth}
\vspace*{-5mm}
\begin{algorithm}[H]
\caption{$\alg{silly-algo}(w,n)$}
\label{alg:silly-algo}
\Input{bitstring $w$ of length $n$}
$i\gets 0$, \lWhile{$w[i]==0$}{$i\gets i+1$}
\tcp{\small$\!w[i]$ is leftmost non-zero, possibly $\$\!\!$}
\lFor*{$k=1$ to $(i{+}1)^2$}{ print ``*'' }
\end{algorithm}
\end{minipage}

	Hint: If you find part (c) difficult, then for partial credit
	state a summation-formula for $T^{\rm avg}(n)$, simplify it
	as much as possible, and give as tight an upper bound for it
	as you can manage. 
	You may use without proof that $x\geq 4\log x$ for $x\geq 16$.
	The course-notes have bounds for some summations that you 
	may use without proof (but state the page-number).

\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 \alg{null})}{\KwRet{``empty tree''}}
	\lWhile{$r$.\alg{leftChild} $!=$ \alg{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\}$.
	
	{Note}: the expected level of rigour is to be as precise
	as we were with our average-case time examples in class
	(Section 1.5 in the notes).

\part{b} Show that $T^{\rm avg}(n)\in O(\log n)$.
	
	{Note}: it is recommended to 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.

	Note: if you choose to use induction, the expected level of rigour
	is as in our bound on the expected length of 
	a random downward walk in a binary tree (Lemma 2.3 in the notes).

	{Aside}: recall that the average height of binary search trees is in $\Theta(\sqrt{n})$, meaning we
	{\em cannot} argue the bound on $T^{\rm avg}(n)$ via the average height.
\end{itemize}

\subsection{[6+3=9 marks]}

\begin{enumerate}
\part{a} 
Assume that you are given a non-empty linked list $L$ that contains $n$ key-value pairs
in sorted order.   Design an algorithm to build a binary search tree that contains
exactly the items of $L$ and that is \emph{perfectly size-balanced}, i.e., 
for every vertex $z$ we have $|\alg{size}(z.\alg{left})-\alg{size}(z.\alg{right})|\leq 1$.
The run-time must be $O(n)$ and the algorithm should use $O(\log n)$ auxiliary
space (i.e., space other than the input linked list $L$ and the output-tree $T$ that you are building).

\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{[2+3+2+4+3+4=18 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} below gives (an 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}
    Design algorithm \alg{lowest-small-ancestor}($z$). This must achieve the
    following:  You are given
    the newly inserted leaf $z$, and you know that the tree is now not height-balanced.  You
    must find an ancestor $x$ of $z$ such that 
        $\alg{size}(x) < \left( \tfrac{4}{3} \right)^{d(x,z)}$.
    Furthermore, your $x$ must be the lowest ancestor of $z$ that satisfies this, i.e.,
    must minimize $d(x,z)$.  The run-time must be $O(\alg{size}(x)+\log n)$.

\part{e}  Suppose now that you have access to the subroutine \alg{lowest-small-ancestor}($z$)
from the previous question that 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)$.

Argue that the rest of the insertion-routine is correct, that is, 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.

\part{f} Let $p$ be the node returned by \alg{lowest-small-ancestor}.  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 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.

\end{document}