\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[normalem]{ulem} % for sout
\usepackage{amsmath,amssymb} 
\def\part#1{\item[\bf #1)]}
\usepackage{enumerate}
\usepackage{tikz}
\usetikzlibrary{patterns,calc,chains,shapes.multipart,arrows,positioning,shapes,automata,fit,shadows,arrows.meta,trees}
\usepackage{xcolor,colortbl}


\newenvironment{spaceForAnswer}
    {\ifthenelse{\isundefined{\suppressSpace}}{\expandafter\comment}{}}
        {\ifthenelse{\isundefined{\suppressSpace}}{\expandafter\endcomment}{}}

% two commands that we need frequently
\def\calI{\ensuremath{\mathcal{I}}}
\def\alg#1{\text{\it #1}}
\DeclareMathOperator{\concat}{%
\raisebox{-0.2ex}{%
\scalebox{0.4}{%
\begin{tikzpicture}[thick]%
\draw[] (0,4ex) arc[start angle=90, end angle=120, radius=0.5];
\draw[] (0,4ex) arc[start angle=90, end angle=60, radius=0.5];
\draw[] (0,0) arc[start angle=270, end angle=300, radius=0.5];
\draw[] (0,0) arc[start angle=270, end angle=240, radius=0.5];
\end{tikzpicture}
}}%
}


% override so that we can use sections for each question
\renewcommand{\thesubsection}{Question \arabic{subsection}}
\newcommand{\smallbox}[2]{}

\begin{document}

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

\subsection{[20 marks]}
\textcolor{red}{Update: 2025-07-23: A leaf should have height 0, not 1.}

Deletion is hard in any tree, but especially hard in B trees and its
variants, as the tree may need to be rebalanced after deletion.  In
this question we will discuss the variant of B trees in which keys
are only stored at the leaves, {\it the B+ tree}.

In practice, database and filesystem implementations relax the B+ tree
invariant to allow for underfilled nodes after deletion, such
as the popular Berkeley Database.  We will call this a {\it relaxed B+ tree}.
A relaxed {\it B+ tree} of order $2b$ will always have at least $b$
items and at most $2b$ items in each leaf and node except after deletion,
which is allowed to underfill nodes.

Insertion and searching proceed as before in a standard B+ tree.

Deletion in such a tree deletes keys and values at leaves,
leaving leaves underfilled until they are empty, at which point
that leaf is deleted.  When such
a leaf is deleted one of the corresponding comparators in its parent
is deleted, until it is empty, in which case its comparator in its
parent is deleted, and so on, and so forth.
An empty node with 1 child is simply skipped over directly
to its child while inserting, searching, and deleting.

\subsubsection{Part 1}
Argue briefly that {\it tombstoning}, i.e lazy deletion,
can be inappropriate in a B+ tree used for implementing
databases or filesystems.

\subsubsection{Part 2}
Argue that a B+ tree of order $2b$ that has had $m$ insertions
and $d$ deletions has height at most:
\[ \log_{b}(\frac{m}{b}) + 1. \]

You will want to use the potential function given by summing
up $\max\{0, j - b\}b^{h-1}$ over each node, where $h$ is the height
of that node and $j$ is the number of items in that node (a leaf has height \textcolor{red}{$0$}).

{\it (This is a recent result of Sen and Tarjan.  You are welcome
  to read the original research paper, but like many research papers
  many of the details are left to the reader.  I expect an analysis
  that is well explained and has the details filled in).}

\subsection{[20 marks]}


\newcommand{\fournode}[1]{\begin{tabular}{@{\vrule width 1pt\,}c@{\,\vrule width 1pt\,}c@{\,\vrule width 1pt\,}c@{\,\vrule width 1pt\,}c@{\,\vrule width 1pt}}\noalign{\hrule height 1pt}#1\\\noalign{\hrule height 1pt}\end{tabular}}
\newcommand{\threenode}[1]{\begin{tabular}{@{\vrule width 1pt\,}c@{\,\vrule width 1pt\,}c@{\,\vrule width 1pt\,}c@{\,\vrule width 1pt}}\noalign{\hrule height 1pt}#1\\\noalign{\hrule height 1pt}\end{tabular}}
\newcommand{\twonode}[1]{\begin{tabular}{@{\vrule width 1pt\,}c@{\,\vrule width 1pt\,}c@{\,\vrule width 1pt}}\noalign{\hrule height 1pt}#1\\\noalign{\hrule height 1pt}\end{tabular}}
\newcommand{\onenode}[1]{\begin{tabular}{@{\vrule width 1pt\,}c@{\,\vrule width 1pt}}\noalign{\hrule height 1pt}#1\\\noalign{\hrule height 1pt}\end{tabular}}

\noindent
\begin{minipage}{0.4\linewidth}
Consider the following 2-4-tree of height 2: 
\end{minipage}
\begin{minipage}{0.5\linewidth}
\vspace*{-3mm}
\begin{tikzpicture}[scale=0.6,level distance=50pt,
    every node/.style={inner sep=0pt},
    level 1/.style={sibling distance=200pt},
    level 2/.style={sibling distance=70pt},
    level 3/.style={sibling distance=32pt}]

    \node (a) {\onenode{34}}
     child {node {\threenode{13&19&28}}
      child {node {\onenode{10}}}
      child {node {\onenode{16}}}
      child {node {\threenode{20&22&25}}}
      child {node {\onenode{31}}}
     }
     child {node {\onenode{40}}
      child {node {\onenode{37}}}
      child {node {\twonode{43&46}}}
     }
;
\end{tikzpicture}
\end{minipage}


\begin{enumerate}
\itemsep -5pt
\item \begin{minipage}[t]{0.3\linewidth}
Show the 2-4 tree that results after doing {\it insert(26)}.
No need to show empty subtrees,  and no justification required.   
\end{minipage}

%

\item \begin{minipage}[t]{0.3\linewidth}
Show the red-black tree that corresponds to the given 2-4-tree
({\bf not} your answer to (a)).  
%You need not show empty subtrees.  No justification required.   
No need to show empty subtrees, no justification required.   

\smallskip
Clearly indicate the color of nodes, by labelling them `red' or `black' 
or by using different shapes as in Question 1(i).
\end{minipage}
\hspace*{1mm}
%\begin{spaceForAnswer}
\begin{minipage}[t]{0.66\linewidth}%
\vspace*{-3mm}%
\smallbox{50mm}{0.993\linewidth}
%\smallbox{50mm}{0.555\linewidth}
\end{minipage}%
%\end{spaceForAnswer}







% TB: I found the following questions hard to phrase precisely, so omit to be safe
%\item Show a 2-4-tree $T$ of height 2 such that the red-black tree $T'$ that
%	corresponds to $T$ has the maximum possible height.
%\answerbox{30mm}
%\item  Assume you have a 2-4 tree $T$ that has height $h$.   
%		Let $T'$ be the corresponding red-black tree.    What is the 
%		smallest and largest possible height of $T'$?
%		Give exact bounds, no asymptotics, and justify your answer
%		by illustrating (for $h=3$) what the corresponding trees $T$ would look like.
%\begin{spaceForAnswer}
%\answerbox{60mm}
%\end{spaceForAnswer}
%\vspace*{\fill}
%

\smallskip
\item Let $T$ be a red-black tree of even height $h\geq 0$.
%Show that levels $0,1,\dots,\lfloor h/2 \rfloor$ are
Show that levels $0,1,\dots,\tfrac{h}{2}$ are
completely full.
\begin{spaceForAnswer}
\answerbox{70mm}
\end{spaceForAnswer}


\end{enumerate}



\subsection{[20 marks]}


One trick to make searching in a dictionary faster is to add an
auxiliary data structure that can tell you with high probablity when
an item is {\em not} in the dictionary.  This works especially well
if the keys are numbers and we can do hashing.

Thus, you would like to create a data structure that supports the
operation IsIn($k$), which returns a boolean value as follows:
	\begin{itemize}
	\item If it returns false, then $k$ is definitely not in the dictionary.
	\item If it returns true, then $k$ is in the dictionary with
		probability $>\frac{1}{2}$.
	\end{itemize}
You will also need the following two operations:
\begin{itemize}
\item UpdateOnInsert($k$): An item with key $k$ is inserted into the main
	dictionary, and your  auxiliary data structure should therefore
	also be updated.
\item UpdateOnDelete($k$): An item with key $k$ is deleted from the main
	dictionary, and your  auxiliary data structure should therefore
	also be updated.  This function will not be called unless $k$
	was indeed a key in the dictionary.
\end{itemize}

Describe an implementation of such a data structure that supports these
three operations in $O(1)$ {\bf worst-case} time, and that uses $O(N)$ space,
where $N$ is a upper bound on the maximum number of items that will be
in the dictionary.
You may assume that you know $N$ beforehand and that you have uniform hash-functions available.









\subsection{[20 marks]}



A {\em MultiMap} is an ADT that allows to store multiple
values associated with keys.  Thus, {\tt Insert}($k,v$) may be called
even if key $k$ already existed in data structure, and it adds the
value $v$ as one of the values associated with $k$.    (You may assume
that $v$ was not previously associated with $k$.)
{\tt Search}($k$) returns {\em 
all} values that are associated with key $k$,
and {\tt Delete}($k$) deletes all of them.

Assume that the keys are uniformly distributed integers.  Let $N$ be the
number of keys and $n$ be the total
number of values that are stored in the dictionary,
noting that $n\gg N$ is possible.
Describe a realization of ADT MultiMap with expected
space $O(n)$, where the operations have the following
run-time:  
{\it insert($k,v$)} has expected time $O(1)$
{\it search($k$)} and {\it delete}($k$) both have
worst-case run-time $O(1 + s)$,
where $s$ is the number of values associated with $k$.
You do not need to give pseudo-code for the methods, but describe
the idea in detail.






\subsection{[20 marks]}



\begin{enumerate}[\bf a)]
\item   (Warm-up.)
	Consider the text $A\,C\,A\,G\,A\,T\,A\,T\,A\,C\,A\,C\,A\,A\,C\,G$
	over alphabet $\Sigma=\{A,C,G,T\}$.

	What is the cost of the corresponding Huffman-encoding?   
	Show how you obtained your answer, and also write the 
	length of the code-word for each character.







\item   Given some probabilities $p_1,\dots,p_s$ (with $0<p_i<1$ and $\sum_{i=1}^s p_i=1$),
	the {\em entropy} is defined to be
		$$H(p_1,\dots,p_s)=- \sum_{i=1}^s p_i \log_2(p_i).$$
	For a text $S$ over alphabet $\Sigma=\{x_1,\dots,x_s\}$, we define the entropy $H(S)$ to be $$|S|\cdot H(p_1,\dots,p_s),$$
	where $p_i = \tfrac{1}{|S|} (\text{frequency of $x_i$})$ is used as ``probability'' of character $x_i$ for $i=1,\dots,s$.

%Sometimes, Huffman-encoding is described in terms of the {\em probability} $p_i$ (of a character $x_i \in \Sigma$),
%which is defined as the frequency of $x_i$ divided by the length of the source text.    
%This probability can in turn be used to derive lower bounds on the length of encodings.
	Compute $H(S)$ for the text from part (a).   Show how you obtained the answer (in particular, list the probabilities).






\item  
Let $S$ be a text such that the length of $S$ and the frequency of the characters $x_1,\dots,x_k$ in $S$ are powers of 2.   
In other words, there exist integers $\ell_0,\dots,\ell_k$ such that $|S|=2^{\ell_0}$ and 
$x_i$ has frequency $f_i=2^{\ell_i}$ for $i=1,\dots,k$.
Show that the Huffman-encoding of $S$ has cost $H(S)$. 

Hint: The text from (a) satisfies the assumption.   Study its Huffman-trie: what can you say about the
length of the encoding of $x_i$?   (For ease of description, assume that the naming is such that
$\ell_1\geq \dots \geq \ell_k$.)






\end{enumerate}
Motivation:  
%The character-probabilities are used to develop a lower
%bound on {\em any} encoding into a bit-string (regardless whether it
%comes from a prefix-free binary encoding or elsewhere).  Namely,
Based on Shannon's information-theoretic lower bound, one can argue that
\emph{any} encoding of $S$ as bit-string (whether obtained via
prefix-free binary encoding or otherwise) has length at least $H(S)$. So in the special
case where the frequencies are powers of 2, Huffman-encoding gives the 
minimum-length encoding that is possible.

 



\end{document}
