\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} 
\usepackage{tikz}
\usetikzlibrary{patterns,calc,chains,shapes.multipart,arrows,positioning,shapes,automata,fit,shadows,arrows.meta,trees}
\def\alg#1{\text{\it #1}}
\renewcommand{\thesubsection}{Question \arabic{subsection}}
\def\part#1{\item[\bf #1)]}

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240E, Winter 2025}\\
\vspace{3mm}
{\Large\bf Assignment 3}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, March 4, 2025 at 5pm}
\end{center}

Be sure to read the assignment guideliness
(\url{https://student.cs.uwaterloo.ca/~cs240e/w25/assignments.phtml#guidelines}).
Submit your solutions electronically to Crowdmark.

\vspace{3mm}

\textbf{Grace period:} submissions made before 11:59PM on Mar. 4 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.

\medskip

\subsection{[5+7=12 marks]}

A \emph{Cartesian tree} is a treap except that the priorities can be arbitrary
values (so are not necessarily a permutation of $\{0,\dots,n{-}1\}$).  This means that
we no longer have the array $P$ that we had for treaps, i.e., we cannot look up
the node that has a given priority.

Let $T$ be a Cartesian tree that has height $h$ and $n$ nodes.    


\begin{itemize}
\part{a}
Describe an algorithm that is
given $T$ and a key $k$, and 
that prints all items in $T$ for which the {\bf key} is at least $k$.
(There is no restriction on the order in which to print them.)
Note that $k$ need not exist as a key in $T$.

To state the desired run-time, we need a small detour.
Let the \emph{output-size} $s$ be the number of items in $T$ for which the key is at least $k$,
and note that $s$ could be anywhere between $0$ and $n$.    Your algorithm
will have to spend $\Omega(s)$ time to print the items, and for this reason
we include $s$ in the desired run-time bound: Your algorithm should have $O(h+s)$ worst-case run-time.

\part{b}
Describe an algorithm that is
given $T$ and a priority $p$, and 
that prints all items in $T$ for which the {\bf priority} is at least $p$.
(There is no restriction on the order in which to print them.)
Note that $p$ need not exist as priority in $T$.
Your algorithm should have $O(1+s)$ worst-case run-time, where $s$ 
is the output-size, i.e., the number of items where the priority is at least $p$.
\end{itemize}

\subsection{[5 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{[3 marks]}

Let $L$ be an unordered list with $n$ distinct items $k_1,\dots,k_n$.
Give a $\Theta$-bound on the expected access-cost
if you put $L$ in the optimal static order for the following frequencies:
$$\text{$f_i = \frac{n!}{i}$ for $1 \leq i \leq n$}$$ 
For example, for $n=4$ we have $n!=24$ and the access-frequencies would be 
$24$, $12$, $8$ and $6$.   Your bound must be in closed-form, simplify 
as much as possible.    

\subsection{[2+2+2+5+4+2(+5)=17(+5) marks]}

\def\pp{\mathtt{++}}
Consider the following algorithm to build a binary search tree:

\begin{algorithm}[H]
\caption{$\alg{build-path-BST}(w,n)$}
\Input{$w$ is a bit-string of length $n$}
$T\gets$ empty binary search tree; $\ell\gets 0$, $r\gets n-1$\;
\For{$(i=0;i<n;i\pp)$}{
	\leIf{$w[i]=0$}{ $k\gets \ell; \ell\pp$}{$k\gets r; r\mathtt{--}$} 
	insert $k$ into $T$ using \alg{BST::insert} (no rotations)
}
\KwRet($T$)
\end{algorithm}

\begin{enumerate}
\part{a} Let $T(w)$ be the tree constructed for bitstring $w$ of length $n$.
Show that $T$ has height $n-1$, i.e., it is a path from the root to a unique leaf. 
\end{enumerate}

Let $T_\mathcal{A}(w)$ (for $\mathcal{A}\in \{\text{MTF}, \text{splay}\}$) 
be the binary search tree obtained as follows:   First build $T(w)$,
and let $z$ be its unique leaf.    Now apply rotations at $z$ until it becomes
the root.  Here we use either the \emph{MTF-heuristic} (i.e., single rotations)
or the \emph{splay-heuristic} (i.e., zig-zig and zig-zag rotations), and $\mathcal{A}$
indicates the applied heuristic.  

\pagebreak

\begin{enumerate}
\part{b} (Warm-up) Assume that we have done rotations until $z$ is the grandchild
	of the root, so up to symmetry the current tree is in one of the following formations:

{\centering
\tikzset{
	subtree/.style={ isosceles triangle, shape border rotate=90, anchor=apex, minimum width=25pt },
	to subtree/.style={ edge from parent path={(\tikzparentnode) -- (\tikzchildnode.north)} },
}
\scalebox{0.8}{
\begin{tikzpicture}[level distance=32pt,
    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=35pt}]
    \node (a) {$g$}
      child{edge from parent[draw=none]}
      child{node {$p$}
        child{node{$z$}
          child{node [subtree] {$A$} edge from parent[to subtree] }
          child{node [subtree] {$B$} edge from parent[to subtree] }
        }
        child{edge from parent[draw=none]}
      };
    \node[draw=none,left=30pt of a] {(i)};
    \node[right=200pt of a] (b) {$g$}
      child{edge from parent[draw=none]}
      child{node {$p$}
        child{edge from parent[draw=none]}
        child{node{$z$}
          child{node [subtree] {$A$} edge from parent[to subtree] }
          child{node [subtree] {$B$} edge from parent[to subtree] }
        }
      };
    \node[draw=none,left=30pt of b] {(ii)};
\end{tikzpicture}
} % scalebox
} % centering

Show what the final tree looks like, for both formations and both heuristics.
(So there are four trees to show in total.)    No justification needed.
\end{enumerate}

The following questions relate the height of $T_\mathcal{A}(w)$ to the height of $T(w)$ (which
we know to be $h:=n-1$ from part (a)).  Let $H_\mathcal{A}(w)$ be the height of $T_\mathcal{A}(w)$ 
and as usual let $H_{\mathcal{A}}^{\rm worst}(n)$,
$H_{\mathcal{A}}^{\rm best}(n)$
be the maximum/minimum of $H_{\mathcal{A}}(w)$ over all bitstrings of length $n$.

\begin{enumerate}
\part{c} Show that $H_{\rm MTF}^{\rm worst}(n)=h$,
	by giving a suitable string $w$ and showing $T(w)$, $T_{\rm MTF}(w)$, and some intermediate
	steps of the transformation.  Your construction should work for {\bf any} $n$
	(give it for a small $n$ of your choice and then explain how to generalize).

\part{d} Show that $H_{\rm splay}^{\rm worst}(n)\leq h/2+1$ if $n$ is odd (so $h$ is even).

	Hint: Bound the height of the subtree at $z$ after $i$ (zig-zig or zig-zag) rotations.   

\part{e} Show that $H_{\rm MTF}^{\rm best}(n)\geq \lceil h/2 \rceil$.    

	Hint: Consider the structure of the two subtrees of $z$ after we have done some rotations.

\part{f} Show that $H_{\rm splay}^{\rm best}(n)<h/2$, 
	by giving a suitable string $w$ and showing $T(w)$, $T_{\rm splay}(w)$,
	and some intermediate steps of the transformation.
	If suffices to do this for {\bf one} odd $n$ (and
	try to keep it small, say $n\leq 17$).

\part{g} (Bonus)   Give an exact bound on $H_{\rm splay}^{\rm best}(n)$
	that depends only on $n$ and uses no asymptotics.
	In other words, state a function $f(n)$, and show that for
	all $n$ that are divisible as needed, you have: (i) $T_{\rm splay}(w)\geq f(n)$ for all
	bitstrings $w$ of length $n$, and (ii) there exists a bitstring $w$ of length $n$ with
	$T_{\rm splay}(w)\leq f(n)$.

	Part-marks will be given if you show only one of the inequalities, as long as your $f(n)$
	is close to the correct answer.
\end{enumerate}

\pagebreak

\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{[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}
