\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{\showMarking}{show them} % comment out this line if not wanted
    % i.e., if you'd like to see suggested marking scheme
%\newcommand{\showAnswerSpace}{show them} % this should usually be enabled
    % disabling it *removes* everything surrounded by "spaceForAnswer"

%%%%%%% a few packages
%\usepackage{fullpage}
\usepackage[letterpaper]{geometry}
\newgeometry{top=40mm,bottom=18mm,left=.5in,right=.5in,footskip=.5in}
%\newgeometry{top=0.5in,bottom=.5in,left=.5in,right=.5in,footskip=.5in}
\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{fancyhdr} 
\usepackage{amsmath,amssymb} 
\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
\newenvironment{solution}
    {\ifthenelse{\isundefined{\showSolution}}
        {\expandafter\comment}{\color{blue}\hfill\break{\bf Solution Ideas}:}}
        {\ifthenelse{\isundefined{\showSolution}}%
        {\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}{}}
\newenvironment{spaceForAnswer}
    {\ifthenelse{\isundefined{\showAnswerSpace}}{\expandafter\comment}{}}
        {\ifthenelse{\isundefined{\showAnswerSpace}}{\expandafter\endcomment}{}}

% two commands that we need frequently
\def\calI{\ensuremath{\mathcal{I}}}
\def\alg#1{\text{\it #1}}

\begin{document}
\begin{center}
\bf CS240E Tutorial, Feb 28, 2025
\end{center}

\begin{enumerate}
\item Which asymptotic relationships hold between $g(n)=n\log n$ and the recursively
	defined function $f(n)$ with $f(1)=0$ and $f(n)=n+\tfrac{2}{n} \sum_{i=1}^{n-1} f(i)$?

\begin{solution}
We have $f(n)\in \Theta(n\log n)$.   This recursive function was the one that
we got as upper bound when analyzing \alg{quick-sort}, and we proved in class that it is
$O(n\log n)$.   We also know that \alg{quick-sort} takes $\Omega(n\log n)$ even in the
best case, and so this function cannot be smaller than that.
\end{solution}

\item Let $T$ be a binary heap of size $n=2^k$ for some integer $k$.   Assume that $T$ is stored as a tree.
	Explain how to build a binomial heap that stores the same items in $O(\log n)$ time.

\begin{solution}
	Since $n=2^k$, it has the right number for one flagged tree.   All we need to do is change the
	structure.   Call $T.\alg{delete-max}$ and store the item in $m$.    What remains of $T$ has
	$2^{k}-1$ nodes, so is a complete binary tree with the heap-order property (hence also
	the binomial heap-order property).   Create a new node with $m$, make it the root, and
	make what remains of $T$ the left subtree.   That's a flagged tree.
\end{solution}

\item \begin{minipage}[t]{0.5\linewidth}
Consider the pseudocode on the right.   What is the
expected run-time?    
\end{minipage}
\hspace*{\fill}
\begin{minipage}[t]{0.44\linewidth}
\vspace*{-6mm}
\begin{algorithm}[H]
\caption{\alg{mystery}(int $n$)}
\lIf{$n\leq 1$}{\KwRet{}}
\lIf{{\it random}$(2)=0$} {\alg{mystery}($\lfloor \tfrac{n}{2} \rfloor$)} 
\lElse{\alg{mystery}($n{-}1$)}
\end{algorithm}
\end{minipage}

\begin{solution}
We analyzed this in the downward walk in the meldable heap.
($T(n)\leq \tfrac{1}{2}T(n/2)+\tfrac{1}{2}T(n-1)+1$)
and this resolves to $O(\log n)$.

This is tight since we at best cut $n$ in half every time, so 
need $\Omega(\log n)$ recursions to reach $n=1$.
\end{solution}


\item \begin{minipage}[t]{0.99\linewidth}
Let $T$ be an AVL-tree.   Assume that you have just now inserted a new key $k$
into $T$, and let $z$ be the node that stores $k$.   Show that $z$ has no 
grandchildren.
\end{minipage}

\begin{solution}
We first do BST::insert, after which $z$ is a leaf.   If no rotation
affects $z$ then it stays a leaf.   Otherwise (say at a rotation $x$-$p$-$g$)
we must have $z=x$ since it has no children.   By the AVL-rotation proof,
imbalance at $g$ means its height was newly increased to $2$, and afterwards
it is back to 1.  Therefore the subtree at $z$ (which stays in the subtree of $g$) 
has height at most 1 afterwards, and $z$ has no grandchildren.
\end{solution}


\item \begin{minipage}[t]{0.99\linewidth}
In the array below, 
{\it interpolation-search}(70) finds the item at the first probe
that uses the formula.
What is the smallest possible integer at $XX$?  

\vspace*{-5mm}
\hspace*{\fill}
\tikzset{chain node/.style={draw,minimum width=4ex,minimum height=5.5mm}}
\begin{tikzpicture}[line width=1pt,scale=0.6,
                    start chain=going right,node distance=-1pt,
                        every label/.style={draw=none,minimum width=0pt,text=blue,font=\tt\footnotesize},
                    label distance=0mm]
  \node[chain node,on chain,label={above:0}] {XX};
  \node[chain node,on chain,label={above:1}] {57};
  \node[chain node,on chain,label={above:2}] {64};
  \node[chain node,on chain,label={above:3}] {70};
  \node[chain node,on chain,label={above:4}] {72};
  \node[chain node,on chain,label={above:5}] {77};
  \node[chain node,on chain,label={above:6}] {81};
  \node[chain node,on chain,label={above:7}] {92};
  \node[chain node,on chain,label={above:8}] {93};
  \node[chain node,on chain,label={above:9}] {99};
  \node[chain node,on chain,label={above:10}] {100};
\end{tikzpicture}
\end{minipage}

\medskip

\begin{solution}
We must have had $m=3$ in the first round, else we wouldn't
find $70$.  So 
$$3=m=\ell+\lceil \frac{70-A[\ell]}{A[r]-A[\ell]}(r-\ell-1) \rceil =0+\lceil  9\frac{70-x}{100-x} \rceil = \lceil \frac{630-9x}{100-x} \rceil.$$
So we must have had $\frac{630-9x}{100-x} \leq 3$ or $630-9x\leq 300-3x$ or $330\leq 6x$ or $55\leq x$. \framebox{55}
\end{solution}

\item Show that for \emph{any} deterministic meldable heap $H$ with $n$ nodes, the operation $\alg{insert}(k)$
	has {\bf worst-case} run-time $O(\log n)$ if we use the child with the not-larger size for 
	breaking ties during merge.

\begin{solution}
Recall from class that \alg{insert} is done by creating a single-node heap $M$ and then merging it
into $T$.    The merge in turn is a downward walk in $T$ (or in $M$, but if we ever walk down in
$M$ then we are immediately done).    

In a deterministic meldable heap, the downward walk is steered by the sizes.   Whenever we go from
a node $z$ to a child $c$, we choose $c$ to have the not-bigger size among the two children.
Therefore, if we had size $N$ at $z$ then we have size at most $N/2$ at $c$.    Since we stop
when we reach an empty subtree, we can halve the size at most $\log n$ times, so we go downward
at most $\log n$ times.
\end{solution}

\item You are given $n$ rectangles $R_0,\dots,R_{n-1}$ that lie on an $n\times n$-grid,
	i.e., the coordinates of all four corners of each rectangle are integers
	in $\{1,\dots,n\}$.

Describe an algorithm that sorts the rectangles by increasing area in $O(n)$ time.

\begin{solution} First compute the $n$ areas and store them in an array $X$.    

Next view $X[i]$ as number in radix-system $R=n$, so 
write $X[i]=A[i] n + B[i]$ with $A[i]= X[i] / n$ and $B[i]= A[i] \% n$; these arrays
$A$ and $B$ can be computed in  linear time.   

Now use part radix sort to sort $X$ in $O(n)$ time.   This takes time $O(m(R+n))$;
since we have $R=n$ and $m=2$ this is $O(n)$ time.
\end{solution}

\item Why is a binary search tree (without any rebalancing) not oblivious?

\begin{solution}
The item at the root was always the first to be inserted, so not
all insertion orders could have happened.
\end{solution}

\item
We have seen \emph{many} variants of binary search trees in class, each with some
advantages and disadvantages with respect to run-time and/or number of rotations.
Create one more variant that satisfies the following constraints:
\begin{itemize}
\itemsep -1pt
\item Key-value pairs are stored in a binary search tree.  Nodes may store additional information.
\item The space is $O(n)$ at all times, where $n$ is the number of currently stored key-value pairs.
\item \alg{search} has $O(\log n)$ worst-case run-time.  
\item \alg{insert} has $O(\log n)$ worst-case and uses at most 1 (single or double) rotation. 
\item \alg{delete} has $O(\log n)$ amortized time and uses no rotations.
\end{itemize}

\begin{solution}
Idea: Use AVL-trees with lazy deletion and re-building as for scapegoat trees.

\alg{search} works exactly as in any binary search trees.  $O(\log n)$ worst-case time since
the height is $O(\log n)$.

\alg{insert} works exactly as in an AVL-tree.  $O(\log n)$ worst-case time, at most 1 rotation.

\alg{delete} mostly uses lazy deletion, i.e., it performs \alg{BST::search}, then marks node as `deleted',
	but keeps the node around (and later searches ignore it).

To keep the space at $O(n)$ at all times, we occasionally need to rebuild.  Namely, whenever there are more
than $n$ items that are marked `deleted', rebuild the entire AVL-tree from scratch as a perfectly balanced
subtree, using only the actual keys (not the deleted ones).    
This happens as part of \alg{delete}, but
uses no rotation.   
\end{solution}
\end{enumerate}

\end{document}
