\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools,algorithm,algorithmicx,algpseudocode,enumitem}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 240 Assignment 3},%
pdfsubject={University of Waterloo, CS 240, Winter 2023},%
pdfauthor={AH}]{hyperref}
%\RequirePackage{pstricks,pst-node,pst-tree} % draw trees, requires using xetex
\newlength{\nodeLength}
\newcommand{\Node}{A}
\newcommand{\setnode}[1]{
  \settowidth{\nodeLength}{#1}
  \renewcommand{\Node}[1]{
    \Tcircle[name=#1]{\makebox[\nodeLength]{##1}}
  }
}
\setnode{99}

\newcommand{\alg}[1]{\ensuremath\mbox{\it #1}}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\renewcommand{\thesubsection}{Question \arabic{subsection}}

\newcounter{algorithmeligne}
\newcommand{\instr}[1]{%\underline
                        {\bf #1}}
\newcommand{\nomproc}[1]{{\rm\bf #1}}
\newenvironment{algorithme}
        {
        \setcounter{algorithmeligne}{0}

        \newcommand{\lign}{
                \stepcounter{algorithmeligne}
                {\footnotesize \arabic{algorithmeligne}.}\>
                }
        \begin{center}
        \begin{tabular}{|c|}
        \hline
        \begin{minipage}{1cm}
        \small
        \,
        \ \ \\[-11mm]
        \begin{tabbing}
\hskip1cm\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\\\kill
        }
        {
        \end{tabbing}
        \ \ \\[-8mm]
        \end{minipage}
        \\\hline
        \end{tabular}
        \end{center}
        }


\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 Winter 2023}\\
\vspace{2mm}
{\Large\bf Assignment 3}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, March 8 at 5:00pm}
\end{center}

\definecolor{care}{rgb}{0,0,0}
\def\question#1{\item[\bf #1.]}
\def\part#1{\item[\bf #1)]}
\newcommand{\balance}[1]{\nodepart{lower}#1} % pseudocode

If you are having difficulties with the assignment, course staff are there to help (provided it isn't last minute). \\
~\\
Please read
\url{https://student.cs.uwaterloo.ca/~cs240/w23/assignments.phtml#guidelines} for guidelines on submission.  
\textbf{Each question must be submitted individually to MarkUs as a PDF} with the corresponding file names: 
a3q1.pdf, a3q2.pdf, ... , a3q6.pdf . 
It is a good idea to submit questions as you go so you aren't trying to create several PDF files at the last minute. \\
~\\
\textbf{Late Policy:} Assignments are due at 5:00pm, with the grace period until 11:59pm.
Assignments submitted after 11:59 on the due date will not be accepted but may be reviewed (by request) for feedback purposes only. \\   
~\\

{\bf{Notes:}}
\begin{itemize}
\item Logarithms are in base 2, if not mentioned otherwise.
\item Array indices start from 0.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{AVL Tree Operations [0+4+3+6=13 marks]}

As discussed in class, it is possible to implement AVL trees such that the nodes store only the balance factor $\{-1, 0, 1\}$ at each node instead of the height of the subtree rooted at the node.

\begin{figure}[h]
\begin{center}\begin{tikzpicture}[%
  level distance=45 pt,
  every node/.style={circle split,draw},
  level 1/.style={sibling distance=200 pt},
  level 2/.style={sibling distance=100 pt},
  level 3/.style={sibling distance=60 pt}%
]
  \node {41 \balance{?}}
    child {node {25 \balance{?}}
      child {node {12 \balance{?}}
        child {node {3 \balance{?}}}
        child {node {17 \balance{?}}}
      }
      child {node {33 \balance{?}}}
    }
    child {node {60 \balance{?}}
      child {node {45 \balance{?}}
        child {edge from parent[draw=none]}
        child {node {47 \balance{?}}}
      }
      child {node {72 \balance{?}}}
    }
  ;
\end{tikzpicture}\end{center}
\caption{Binary tree $T$ for question 1 \label{tree}}
\end{figure}
\begin{itemize}
\part{a}
\textbf{Practice} (not worth any marks): Starting from an empty AVL tree, insert the following keys in order. You should obtain the tree shown in figure 1.
$$41, 72, 33, 45, 60, 25, 3, 12, 17, 47$$
\part{b}
Show the process of inserting the key 15 into the tree in figure 1. Specifically, draw the tree, with balance factors, after the initial BST \texttt{insert} and after each call to \texttt{restructure}.
\part{c}
Suppose the key 41 were deleted from the \emph{original} tree in figure 1. Would this cause a tree rotation? Briefly justify.
\part{d}
Show the process of deleting the key 72 from the \emph{original} tree in figure 1. Specifically, draw the tree, with balance factors, after the initial BST \texttt{delete} and after each call to \texttt{restructure}.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{AVL Tree Height [3+3+3=9 marks]}
In this question, we will prove a recurrence for the height of an AVL tree that leads to a tighter bound (i.e. a lower constant factor) than the proof shown in class.

Let $T_h$ be an AVL tree of height $h$ with a \textbf{minimum} number of nodes. Let $N(h)$ be the number of nodes and $N_L(h)$ the number of leaves of $T_h$.

Recall from class that $T_h$ can be viewed recursively as a tree containing a root with two, possibly empty, subtrees $T_{h-1}$ and $T_{h-2}$.
\begin{itemize}
\part{a} 
Prove that for $h \ge 1$, $N(h) = N(h-1) + N_L(h)$.
\part{b}
Prove that for $h \ge 0$, $N_L(h) = F(h+1)$, where $F(i)$ is the $i$th Fibonacci number. ($F(0) = 0$, $F(1) = 1$, $F(n) = F(n-1) + F(n-2)$)
\part{c}
Prove that for $h \ge 0$, $N(h) = F(h+3)-1$. You must use parts a) and b) to prove c).
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Merging AVL Trees [3+4=7 marks]}
\begin{itemize}
\part{a}
Describe an algorithm \texttt{Join}$(T_A, T_B, h_A, h_B)$ which merges two AVL trees $T_A$ and $T_B$ whose initial heights $h_A$ and $h_B$ are given. You may assume that:
\begin{enumerate}[label=\roman*]
\item Every key in $A$ is less than every key in $B$.
\item $h_A$ and $h_B$ differ by at most one. \label{a-height}
\end{enumerate}

Your algorithm must run in time $O(h_A + h_B)$. Justify that your algorithm produces a valid AVL tree and that it runs in the specified runtime.

\textbf{Erratum:} The nodes in $T_A$ and $T_B$ are labeled with heights, not balance factors.

\part{b}
Describe an algorithm \texttt{Join2}$(T_A, T_B, h_A, h_B)$ as in part a), except that assumption \ref{a-height} is replaced by the following:
\begin{enumerate}[resume*]
\item $h_A < h_B$
\end{enumerate}

As in part a), justify that your algorithm produces a valid AVL tree and that it runs in $O(h_A + h_B) = O(h_B)$ time.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Bounded-Height Skip Lists [4+4=8 marks]}
Suppose you have a skip list with only three levels. The lower level has $n+2 $ entries $-\infty < a_0 < \cdots < a_{n-1} < +\infty$. The middle one has $k+2$ entries, where $k$ is an integer that divides $n$ (so that $n = mk$ for some integer $m$); we assume that (with the exceptions of $\pm \infty$), these entries are evenly spread out so they correspond to $-\infty, a_0, a_m, a_{2m}, \ldots, a_{(k-1)m}, +\infty$. The top level holds $-\infty, +\infty$.

\begin{itemize}
\part{a}
What is the worst-case running time for a \texttt{search} on this list? Give a $\Theta(\ldots)$ expression involving $k$ and $n$, and justify your answer.
\part{b}
For a given $n$, explain how to choose $k$ to minimize the worst-case running time. Prove that your choice of $k$ is optimal and give a $\Theta(\ldots)$ bound on the worst-case running time given your choice of $k$.

\textbf{Erratum:} Your choice of $k$ does not need to divide $n$.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Interpolation Search [3+4+4=11 marks]}
\begin{itemize}
\part{a}
Execute interpolation search for the key $k = 120$ in the following array:
$$[0, 1, 2, 3, 4, 5, 10, 15, 20, 25, 30, 40, 42, 50, 60, 70, 75, 80, 120, 125, 144, 150, 175, 190, 199, 200]$$
For each iteration of the loop, your answer must include the values of $\ell$ and $r$ at the start of the iteration, as well as the value of $m$, if any, computed in that iteration.

\part{b}
Consider interpolation search on a sorted array $A[0,\ldots,n-1]$ that stores real numbers. Suppose that $A[i] = ai + b$ for all $i\in\{0,\ldots,n-1\}$, where $a$ and $b$ are real numbers and $a\neq 0$. For example if $A = \{5, 7, 9, 11, 13, 15\}$ then $a = 2$ and $b = 5$. Prove that the interpolation search on $A$ takes $O(1)$ (no matter if the search is successful or unsuccessful).

\part{c}
Recall that the worst-case search time for interpolation search is $\Theta(n)$. Give a family of an arrays $A_n$, each with $n$ distinct values, (i.e., by defining $A_n[i] = f(i)$ for some function $f$) as well as search keys $k_n$ such that searching for $k_n$ in $A_n$ has runtime $\Theta(n)$. (There are many examples of such inputs, but you only need one for each $n$). You must prove the runtime of the algorithm on your inputs is in $\Theta(n)$.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Trie Operations [2+2+3+3 = 10 marks]}
In this question, when drawing tries, follow the convention that \$ is always to the left of 0, and 0 is always to the left of 1.

\begin{itemize}
\part{a}
Draw the standard (uncompressed) binary trie on the following keys:
$$1001, 001, 1111, 10110, 10, 11, 10100, 1, 000, 101, 00$$
Add \$ to the keys as necessary.
\part{b}
Repeat part (a), except use a compressed trie.
\part{c}
Draw the result of inserting the keys 100 and 1010 into your answer for part (a).
\part{d}
Draw the result of deleting the keys 10100, 11, and 1001 from your answer for part (b).
\end{itemize}

\end{document}
