\documentclass[12pt]{article} 

%%%%%%%% version control
\newcommand{\showSolution}{show them} % comment out this line if not wanted
    % i.e., if you'd like to see suggested solutions
\newcommand{\showFullSolution}{show them}
    % i.e., if you'd like to see fully formed solutions.    They sometime build on top of the ideas, so enable those too
\newcommand{\showMarking}{show them} % comment out this line if not wanted
    % i.e., if you'd like to see suggested marking scheme

%%%%%%% 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}


%%%% a few things that are needed for the data base, but mostly ignored here
\ifthenelse{\isundefined{\showFullSolution}}{}{    % full solution should also show solution sketch
	\ifthenelse{\isundefined{\showSolution}}{\newcommand{\showSolution}{show them}}{} }
\newenvironment{solution}
	{\ifthenelse{\isundefined{\showSolution}}
		{\expandafter\comment}{\color{blue}\hfill\break{\bf Solution Ideas}:}}
        {\ifthenelse{\isundefined{\showSolution}}%
		{\expandafter\endcomment}{}}
\newenvironment{fullsolution}
    {\ifthenelse{\isundefined{\showFullSolution}}
        {\expandafter\comment}{\color{blue}\hfill\break{\bf Solution (more details)}:}}
        {\ifthenelse{\isundefined{\showFullSolution}}%
        {\expandafter\endcomment}{}}
\newenvironment{authorship}{\expandafter\comment}{\expandafter\endcomment}
\newenvironment{usage}{\expandafter\comment}{\expandafter\endcomment}
\newenvironment{suggestedMarkingScheme}
    {\ifthenelse{\isundefined{\showMarking}}
        {\expandafter\comment}{\color{brown}\hfill\break{\bf Marking Ideas}:}}
        {\ifthenelse{\isundefined{\showMarking}}%
        {\expandafter\endcomment}{}}

% 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, Spring 2026}\\
\vspace{3mm}
{\Large\bf Written Assignment 3}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, June 30, 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} AID02.

\textbf{Grace period:} submissions made before 7:59pm on June 30 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{[8 marks]}

Recall the idea of lazy deletion in a sorted array $A$:  You mark items
as `deleted' (rather than actually removing them), and you rebuild
the entire array if the number of `deleted' items is bigger than
the number $n$ of non-deleted items in $A$.  
As a consequence of this rebuild, no items marked `deleted' are left.
The operations have the following actual run-times (you need not prove this).
\begin{itemize}
\item \alg{search}: $\Theta(\log n)$
\item \alg{insert}: $\Theta(n)$
\item \alg{delete} without rebuilding: $\Theta(\log n)$.
\item \alg{rebuild} (as part of \alg{delete}): $\Theta(n)$.
\end{itemize}

Show that the amortized run-time of \alg{search} and \alg{delete}
is in $O(\log n)$, while the amortized run-time of \alg{insert}
is in $O(n)$.

Hint: you may use ``the number of deleted items"
as the potential function.

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

Recall that the {\textsc 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[(a)] Argue that any comparison-based algorithm for {\textsc Selection}
on $n$ keys must have $\Omega(\log n)$ worst-case time.

\item[(b)] 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{[2+6=8 marks]}

\begin{enumerate}
\part{a} Consider the following array $A$ of size $10$:
\tikzset{chain node/.style={draw,minimum width=5mm,minimum height=5.5mm}}
\begin{tikzpicture}[line width=1pt,
                    start chain=going right,node distance=-1pt,
                    every label/.style={draw=none,minimum width=0pt,minimum height=1ex,text=blue,font=\tt\footnotesize},
                    label distance=0mm]
\useasboundingbox (-1,-0.5) rectangle (12,0.5);
{\node[chain node,on chain,label={above:0}] {10};}%
\node[chain node,on chain,label={above:1}] {20};%
{\node[chain node,on chain,label={above:2}] {30};}%
{\node[chain node,on chain,label={above:3}] {40};}%
{\node[chain node,on chain,label={above:4}] {50};}%
{\node[chain node,on chain,label={above:5}] {60};}%
\node[chain node,on chain,label={above:6}] {70};%
\node[chain node,on chain,label={above:7}] {80};%
\node[chain node,on chain,label={above:8}] {90};%
\node[chain node,on chain,label={above:9}] {100};%
\end{tikzpicture}

Show the result of performing \alg{interpolation-search}($A$,10,55) in this array,
by indicating for each round the current values of $\ell,r$ and the
values used for the computation of $m$.

For your convenience, the pseudo-code of \alg{interpolation-search}
is given below.

\begin{minipage}{\linewidth}
\begin{small}
 \begin{algorithm}[H]
        \caption{\alg{interpolation-search}($A,n,k$)}
        $\ell \gets 0$, $r \gets n-1$ \;
        \While{$(\ell \leq r)$} {
        \lIf{($k<A[\ell]$)}{ \KwRet{``not found, would be between indices $\ell-1$ and $\ell$''}}
        \lIf{($k>A[r]$)}{ \KwRet{``not found, would be between indices $r$ and $r+1$''}}
        \lIf{($k=A[r]$)}{ \KwRet{``found at index $r$''}}
                $m \gets  \ell + \lceil \frac{k - A[\ell]}{A[r]-A[\ell]} \cdot (r - \ell-1) \rceil $ \;
                \lIf{($A[m] = k)$} {\KwRet{``found at index $m$''}}
                \lElseIf{$(A[m]<k)$} {$\ell \gets m + 1$}
                \lElse{$r \gets m - 1$}
        } % While
\end{algorithm}
\end{small}
\end{minipage}

\part{b} 
Consider a sorted array $A[0..n{-}1]$ 
where $A[i] = ai + b$ for $0 \leq i \leq n - 1$ 
(for some constants $a >0$ and $b$ that are arbitrary real numbers).
Show that $\alg{interpolation-search}(A,n,k)$ always takes $O(1)$ time, 
regardless of whether key $k$ is in $A$ or not.

\end{enumerate}

\subsection{[4 marks]}

Let $S$ be a skip list that stores $n\geq 4$ non-sentinel keys.  Assume that the lists $L_0,L_1,\dots,L_h$ 
of $L$ have the following property for all $0\leq i<h$.  
\begin{quotation}
If $|L_i|=1$ then $|L_{i+1}|=0$.  If $|L_i|>1$, then $|L_{i+1}|\leq \sqrt{|L_i|}$.
\end{quotation}
(As in class, $|L_i|$ denotes the number of non-sentinels in list $L_i$.)
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 values of $n$.
(But part-marks may be given otherwise.) Justify your answer.

Hint: You might want to draw yourself a skip-list for $n=4$ that satisfies the properties
and verify that your bound is tight for this $n$.  Part-marks for this.

\subsection{[1+2+9+5+4=21 marks]}
This assignment asks you to compare the performance of the MTF-heuristic
for binary search trees with splay trees.

\begin{enumerate}
\part{a}
\begin{minipage}[t]{0.8\linewidth}
Consider the binary search tree shown on the right.  
\begin{itemize}
\part{i}
What is its potential function value when viewed as a splay tree?
(State it with two fractional digits.)  
\part{ii}
Show the binary search tree that results if you perform \alg{splayTree::search}(50).
\end{itemize}

For both part-questions, it suffices to state the correct final answer
but we recommend showing some intermediate steps so we can give part-marks in case of errors.
\end{minipage}
\begin{minipage}[t]{0.1\linewidth}
\mbox{}
\scalebox{0.8}{%
\begin{tikzpicture}[level distance=29pt,
    every node/.style={circle,draw,minimum size=20pt},
    level 1/.style={sibling distance=64pt},
    level 2/.style={sibling distance=64pt},
    level 3/.style={sibling distance=32pt}]
        \useasboundingbox (-2,0) rectangle (5,-6);
    \node {70}
      child{node {20}
        child{edge from parent[draw=none] }
        child{node{30}
          child{edge from parent[draw=none] }
          child{node {40}
            child{edge from parent[draw=none] }
            child{node {60}
              child{node {50}}
              child{edge from parent[draw=none] }
            }
          }
        }
      }
      child{edge from parent[draw=none] }
    ;
\end{tikzpicture}
} % scalebox
\end{minipage}

\part{b} Let $T$ be a binary search tree with $n$ nodes and height $h=n-1$,
        i.e., $T$ is a path from the root to a unique leaf $x$.  Show that
        if we perform {\it splayTree::search}($k$) for the key $k$ at $x$,
        then the resulting tree $T'$ has height at most $h/2+c$ for some
        constant $c$.  Make $c$ as small as possible.  

        Hint: Show a bound on the height of the subtree rooted at $x$
        after you have done $i$ operations.
        
\part{c} Create an example of a binary search tree $T$ with $n$ nodes 
        and a sequence of $\Theta(n)$ operations {\it BST-MTF::search} 
        for keys in $T$ such that the total number of rotations
        is in $\Theta(n^2)$.
        
\part{d} Prof.~I.N.Correct claims that for any $n$ they have an example 
        of a binary search tree $T$ with $n$ nodes 
        and a sequence of $n$ operations {\it SplayTree::search} 
        for keys in $T$ such that the total number of rotations
        is in $\Theta(n^2)$.    In particular the actual run-time
        for these $n$ operations is in $\Omega(n^2)$.

        Prove that this is impossible.
\end{enumerate}

\subsection{[5 marks]}

This question involves a set $S=\{x_0,\dots,x_{n-1}\}$ of infinite-precision
numbers.  Specifically, each $x_i$ is in $[0,1)$ and is written in base-2.  
It is given to you implicitly, via an accessor-function {\it get-decimal-place}$(i,d)$
which returns the bit in the $d$th decimal place of $x_i$.
For example, if $x_i=0.001001...$ then 
{\it get-decimal-place}$(i,3)=1$
and {\it get-decimal-place}$(i,4)=0$.
Function {\it get-decimal-place} takes $\Theta(1)$ time.
The numbers in $S$ have been randomly and uniformly chosen from the interval $[0,1)$
and are all distinct.    

Give an algorithm that finds a longest
common prefix among the numbers in $S$, i.e., a number $y=0.y_1y_2y_3\dots y_s$ such
that there are at least two numbers in $S$ that begin with $y$, and for
which $s$ is as large as possible.    (Note that $y$ is not
necessarily unique, but $s$ is.) The worst-case run-time should be $O(sn)$,
though significant partial credit will be given for an
expected run-time of $O(n(s+\log n))$.

\end{document}