\documentclass[12pt]{article}
\usepackage{fullpage,url,amssymb,epsfig,color,xspace,tikz,amsmath}
\usepackage{algorithm,algorithmic,amsthm, forest}
\usetikzlibrary{shapes,positioning,calc,chains}
\usepackage{hyperref}
\hypersetup{
colorlinks=true,
linkcolor=blue,
filecolor=red,
urlcolor=red,
}
\urlstyle{same}
\renewcommand{\thesubsection}{Problem \arabic{subsection}}
\newcommand{\quesbox}[2]{\begin{center} \framebox[.5\textwidth]{%
\raisebox{-5mm}[0mm][#1]{\begin{minipage}[t]{.45\textwidth}%
{\normalsize\sf #2}{\phantom{ans}}\end{minipage}}} \end{center}}
\begin{document}
\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 - Spring 2020}\\
\vspace{2mm}
{\Large\bf Assignment 3}\\
\vspace{3mm}
\textbf{Due Date: Wednesday July 8, 5pm}
\end{center}
The integrity of the grade you receive in this course is very
important to you and the University of Waterloo. As part of every
assessment in this course you must read and sign an Academic Integrity
Declaration before you start working on the assessment and submit it
{\bf before the deadline of July 8} along with your answers to the assignment --
i.e. {\bf read, sign and submit A03-AcInDe.txt now or as soon as
possible}. The agreement will indicate what you must do to ensure
the integrity of your grade. If you are having difficulties with the
assignment, course staff are there to help (provided it isn't ``last
minute'').
{\bf The Academic Integrity Declaration must be signed and submitted on time or the assessment will not be marked.}
Please refer to the course webpage for guidelines on submission.
Submit your written solutions electronically as a PDF with file name
a3Submit.pdf using MarkUs. We will also accept individual question
files named a3q1.pdf, a3q2.pdf, \dots if you wish to submit questions
as you complete them.
For all questions asking you to design an algorithm, you should include a description of the method, justification of correctness, and runtime analysis.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[7 marks]}
Let $A$ be an unsorted array of $n$ integers in the range $[0, n^{42}]$.
Design an algorithm that finds the minimum (non-negative) difference between any two numbers in this array.
For instance, if the input was $[82, 32, 55, 78, 148]$, then the answer would be $4$, witnessed by the pair $78$ and $82$.
Your algorithm must take $O(n)$ time.
It is important that your solution is explicit about how you represent the data.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[7 marks]}
We want to prove the following: there is no comparison-based algorithm
that can merge $m$ sorted arrays of length $m$ into a unique sorted
array of length $m^2$ doing $O(m^2)$ comparisons. We argue by
contradiction, and we assume that it is possible, so that we have such
an algorithm (which we call FastMerge).
Modify MergeSort in order to use FastMerge, and derive a
contradiction. You may need to solve the following recurrence relation:
$T(n) = \sqrt{n} T(\sqrt{n}) + O(n)$.% Do not worry about $n$ being a perfect square or not.
When solving this recurrence, you can disregard issues relating to the fact that $\sqrt{n}$ is not necessarily an integer.
As a hint, the solution gives $T(n)$ to be $\in \omega(n)$ and $\in o(n \log n)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[4+4 marks]}
This question is about insertion and deletion of elements in an AVL Tree.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}
\item Consider the AVL tree shown in Figure~\ref{avl}. Draw the tree again while replacing $b_0, b_1, \ldots, b_{9}$ with the respective balance factors (i.e., the height of the right subtree minus the height of the left subtree) on each node. A few have been filled in for you as an example.
Perform the operation {\sf Insert(5)} on the tree. Draw the tree
before each rotation (including the intermediate tree in a double
rotation), if any, and draw the final tree. Keep the balance factors
updated up until any call to {\sf fix} is required.
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[
every node/.style = {draw, shape = circle split, grow = down},
level 1/.style={sibling distance = 200pt},
level 2/.style={sibling distance = 100pt},
level 3/.style={sibling distance = 60pt},
level distance = 40pt]
% Quick guide on how to draw an AVL tree
% with balance factors
%
% Leaf Node:
% node{KEY\nodepart{lower}BALANCE}
%
% Parent Node
% node{KEY\nodepart{lower}BALANCE}
% child{LEFT_CHILD_NODE}
% child{RIGHT_CHILD_NODE}
%
% Can replace "child{NODE}" with "child[missing]"
% to indicate no right/left child
%
% Can label nodes with (LABEL) after "node"
% but this is not needed
%
% Tree should begin with "\" before the root node
% and end with ";" after closing all the braces "}"
% in the rightmost node.
%
\node(z){45\nodepart{lower}$b_0$}
child{
node{27\nodepart{lower}$b_1$}
child{
node{7\nodepart{lower}$-1$}
child{
node{3\nodepart{lower}$0$}}
child[missing]}
child{
node{31\nodepart{lower}$b_2$}}}
child{
node{58\nodepart{lower}$b_3$}
child{
node{53\nodepart{lower}$b_4$}
child{
node{49\nodepart{lower}$b_5$}
child[missing]
child{
node{51\nodepart{lower}$b_6$}}}
child{
node{56\nodepart{lower}$b_7$}}}
child{
node{72\nodepart{lower}$b_{8}$}
child[missing]
child{
node{80\nodepart{lower}$b_{9}$}}}};
\end{tikzpicture}
\end{center}
\caption{AVL tree of problem 3.}\label{avl}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Consider the tree in Figure~\ref{avl} (\textit{not} the tree obtained after the insertion in part a). Perform the operation {\sf delete(27)} on the tree, swapping with the inorder successor. Draw the tree before each rotation (including the intermediate tree in a double rotation), if any, and draw the final tree. Keep the balance factors updated up until any call to {\sf fix} is required. Draw the final tree with balance factors.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[4+6 marks]}
Suppose you wish to modify an AVL tree so as to support an operation
{\tt ithSuccessor}, in addition to the standard operations {\tt
insert, delete, find}. The operation {\tt ithSuccessor} takes two
parameters, $x$ and $i \ge 0$, and returns the $i$th inorder successor
of the node $x$. We will always assume that this successor exists (but
maybe not in the subtree rooted at $x$). For $i=0$, this is $x$
itself.
We assume that the nodes have the following fields:
\begin{itemize}
\item {\tt key} -- the key of the node;
\item {\tt left} -- pointer to the left child;
\item {\tt right} -- pointer to the right child;
\item {\tt balance} -- balance factor of the node;
\item {\tt parent} -- pointer to the parent of the node;
\item {\tt isLeft} -- is true if the node is a left child of its parent;
\item {\tt isRight} -- is true if the node is a right child of its parent;
\item {\tt numLeft} -- holds the number of nodes in the left subtree of the node;
\item {\tt numRight} -- holds the number of nodes in the right subtree of the node.
\end{itemize}
\medskip
\begin{enumerate}
\item Give an algorithm {\tt ithNode(x, i)} which returns the $i$th
inorder node in the subtree rooted at $x$, assuming that this
subtree has at least $i$ elements. Hence, $i=1$ corresponds to the
min element in the subtree, and $i=m$ (where $m$ is the number
of nodes in the subtree rooted at $x$) corresponds to the max element in the
subtree. Your algorithm should take time $O(\log(m))$; don't forget
to justify why.
\item Give the algorithm for {\tt ithSuccessor(x, i)}, ensuring that
this operation takes time $O(\log(n))$, if $n$ is the number of nodes
in the whole AVL (again, don't forget to justify why). Hint:
determine if there are enough nodes in your right subtree; if so,
find the $i$th successor there. Otherwise, you will have to go up
the tree, and discuss whether $x$ is a left or right child. You
should use the algorithm {\tt ithNode(x, i)} you just wrote.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[3+3+2+2+3+7 marks]}
The goal of this problem is to show that deleting a single item in
an AVL-tree of height $h$ may require $\lfloor h / 2 \rfloor \in \Omega(h)$ rotations.
Define a family $(T_h)_{h \ge -1}$ recursively in the following
manner: $T_{-1}$ is empty and $T_0$ is a single node; to form $T_h$, we
start with a single node and take a copy of $T_{h-2}$ and a copy
of $T_{h-1}$ as the left and the right children of the root, respectively.
\begin{enumerate}
\item Draw $T_0,\dots,T_4$.
\item For $h \ge 0$, what is the height of $T_h$? Prove your claim.
\item Prove that for $h \ge 0$, $T_h$ satisfies the balance
requirements of an AVL tree.
\item On $T_3$, what are the leaves which require $\lfloor h/2 \rfloor = \lfloor
3/2 \rfloor = 1$ rotation upon deletion? Pick one and show
the resulting tree.
\item Same question with $T_4$, but now with $\lfloor h/2 \rfloor = \lfloor
4/2 \rfloor = 2$ rotations.
\item Prove by induction that for $h \ge 0$, there exists a leaf
$\ell_h$ in $T_h$ such that deleting $\ell_h$ causes $\lfloor h/2 \rfloor$ rotations and the resulting tree has height $h-1$.
Remember to ensure your solution has all the components of a complete inductive proof.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[4+6+4 marks]}
\begin{enumerate}
\item Starting with an empty skip list, insert the seven keys
$54, 15, 51,53, 47,68,36$.
Draw your final answer as on Slide 7 in Module 5.
Use the following coin
tosses to determine the heights of towers (note, not every
toss is necessarily used):
$$T,T,H,H,T,H,T,H,H,T,H,H,T,T,H,T,H,H,T,T,H,H,H,T,\ldots$$
\item The worst case time for searching in a singly linked list
is $\Theta(n)$. Now consider a variation of a skip list which
has fixed height $h=3$ even though $n$ can become arbitrarily large.
Level $S_0$ contains the keys $-\infty,k_1,k_2,\ldots,k_n,\infty$.
Level $S_3$ contains only $-\infty$ and $\infty$.
Describe subsets of keys that should be included in levels $S_1$
and $S_2$ so that searching in the skip list has worst case cost
$\Theta(n^{1/3})$. Provide justification for the runtime of your skip list.
\item
Consider a skip list in which we build new towers as follows:
\begin{quote}
When adding an element to the skip list, we flip two coins at the
same time, until we see at least one tail. The number of times we
toss both coins and obtain two heads is the height of the tower.
\end{quote}
Using the method for building heights described in the above quote,
derive the expected height of any single tower (not the entire skip list).
{\color{red} You may use the following equality without proof: for any $0 < p < 1$, $\sum_{i=0}^\infty i p(1-p)^{i} = \frac{1-p}{p}$.}
\end{enumerate}
\end{document}