\documentclass[12pt]{article}

\usepackage{algo,tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools,algorithm}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 240 Assignment 3},%
pdfsubject={University of Waterloo, CS 240, Spring 2021},%
pdfauthor={MP}]{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{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\renewcommand{\thesubsection}{Problem \arabic{subsection}}
\renewcommand{\thesubsection}{Problem \arabic{subsection}}
\newcommand{\alg}[1]{\ensuremath\mbox{\it #1}}
\newcommand{\pc}[1]{{\bf #1}}

\DeclareUnicodeCharacter{2212}{-} 

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 Spring 2021}\\
\vspace{2mm}
{\Large\bf Assignment 3}\\
\vspace{3mm}
\textbf{Written Questions Due: Wednesday, June 30 at 5:00pm} \\
\textbf{Programming Question Due: Wednesday, July 7 at 5:00pm}
\end{center}

\definecolor{care}{rgb}{0,0,0}
\def\question#1{\item[\bf #1.]}
\def\part#1{\item[\bf #1)]}
%\newcommand{\pc}[1]{\mbox{\textbf{#1}}} % pseudocode
~\\
~\\
~\\

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 \textbf{before the deadline of June 30th} along with your answers to the 
assignment; i.e. \textbf{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). \\
~\\
\textbf{The Academic Integrity Declaration must be signed and submitted on time or the
assessment will not be marked.} \\
~\\
Please read
\url{http://www.student.cs.uwaterloo.ca/~cs240/s21/guidelines.pdf} 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, ... , a3q5.pdf, avlskip.cpp . \\
~\\
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{Remember, late assignments will not be marked.} \\
Late assignments, however, can be reviewed for \textbf{feedback only} upon request to the ISAs at cs240@uwaterloo.ca.
~\\
Note: you may assume all logarithms are base 2 logarithms:  $\log = \log_2$.
~\\
~\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
{\bf You may use the following notation for \emph{AVL} ADT in any of your solutions}: The key stored in a node $v$ is denoted by $\mathit{key}(v)$; the root of \emph{T}  is denoted by $\mathit{root}(T)$; parent node, left and right child of a node $v$ is denoted by  $\mathit{parent}(v)$, $\mathit{leftchild}(v)$ and $\mathit{rightchild}(v)$ respectively; the height of the subtree rooted at \emph{v}  is denoted by $\mathit{height}(v)$.\\
You may assume that all of them are of $O(1)$ running time.\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{[3+3+3=9 marks]}
Let $T_h$  be an $AVL$  tree of height $h$ with \textbf{minimum} number of nodes. Let $N(h)$ be the number of nodes and $N_L(h)$ be the number of leaves  of $T_h$, respectively. \\ Note that $T_h$ can be viewed recursively
as a tree containing a root r with two, possibly empty, subtrees $T_{h−1}$ and $T_{h−2}$.\\

\begin{enumerate}
\part{a} Prove that for $h \geq 1$, $N(h) = N(h-1) + N_L(h)$. \\
\part{b} Prove that for $h \geq 0$, $N_L(h) = F(h+1)$, where $F(i)$ is the $ith$ $Fibonacci$ number. ($F(0)=0,  F(1)=1,  F(2)=1,  F(3)=2 \ldots$) \\
\part{c} Prove that for $h \geq 0$, $N(h) = F(h+3) - 1$. You must use parts a and b to prove c. \\

Note that the analysis in this question can help to put a tighter bound on the height of \emph{AVL} tree.\\
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{[10 marks]}
Given two \emph{AVL trees T1} and \emph{T2}, where the largest key in \emph{T1} is less than the smallest key in \emph{T2}, \emph{Join(T1,T2)} returns an \emph{AVL tree} containing the union of the elements in \emph{T1} and \emph{T2}. Give an algorithm (in pseudocode) for \emph{Join} that runs in time $O(\log n)$, where \emph{n} is the size of the resulting \emph{AVL tree}. Justify the correctness and efficiency of your algorithm.\\
Assume the height of\emph{ T1} is greater than or equal to the height of\emph{ T2}; the other case is symmetric.\\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\subsection{[12 marks]}
Design an \emph{ADT} containing integers that supports the following methods. Show in pseudocode how to implement each of these methods in the requested time.  You must solve this problem with $O(n)$ auxiliary space.\\
~\\
\begin{tabular}{|l|l|l|} 
 \hline
 method & purpose & time \\ 
  \hline
 \emph{init()} & initialize the \emph{ADT} & $O(1)$ \\ 
  \hline
 \emph{insert(x)} & insert \emph{x} into\emph{ ADT}, if it is not in the  \emph{ADT} yet & $O(\log n)$ \\ 
  \hline
 \emph{delete(x)}& delete \emph{x} from \emph{ADT}, if it exists & $O(\log n)$ \\ 
  \hline
 \emph{delete\_ith(i)} & delete the element from\emph{ ADT} which has timestamp equals to \emph{i} as determined & $O(\log n)$ \\ 
  &  by the timestamp order of insertion &  \\ 
  \hline
 \emph{get\_index(x)} & return the place/index (which is determined by the order & $O(\log n)$ \\ 
  & of insertion) of \emph{x}. if \emph{x} doesn't exist, return -1  &  \\ 
 \hline
\end{tabular}
~\\
~\\
\textbf{Note1:} timestamps are assumed to take $O(1)$ space.\\
\textbf{Note2:} timestamp starts with 0.
~\\
For example, after initialization, and calling \emph{insert(3)}, \emph{insert(5)}, \emph{insert(11)}, \emph{insert(4)},\emph{insert(7)},\emph{delete(5)}; \emph{get\_index(7)} returns 4, and \emph{delete\_ith(2)} will delete 11 from the ADT.\\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{[6+6=12 marks]}
\begin{enumerate}
\part{a} Draw a diagram of a skip list starting with an empty one, insert the seven keys
      $67, 28, 64, 66, 60, 81, 49$.
      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$$
\part{b} 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 runtime of
      $\Theta(n^{1/3})$.  Provide justification for the runtime of your
      skip list. You may assume that $n$ is a power of $3$.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\subsection{[3+3+3=9 marks]}

Consider the list of keys:
\[
[1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10]
\]
and assume we perform the following searches:
\begin{center}
9, 5, 2, 6, 4$^\star$, 4, 1, 5, 3, 9$^\star$, 2, 8, 2, 9$^\star$ 
\end{center}
\begin{enumerate}
\part{a} Using the move-to-front heuristic, give the list ordering after the
starred ($\star$) searches are performed. Additionally, 
record the number of comparisons between keys after each search, as well
as the total number of comparisons.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c||c|} \hline
9 &  5 &  2 &  6 &  4 & 4 & 1 & 5 & 3 & 9 & 2 & 8 & 2 & 9  & Total \\ \hline
& & & & & & & & & & & & & & \\ \hline
\end{tabular}
\end{center}
\part{b} Repeat part (a), using the transpose heuristic instead
of the move-to-front heuristic.
\part{c} Another heuristic is \textit{move-to-front2 (MTF2)} that is similar to
\textit{move-to-front (MTF)} except that when an element is found at position $i$
it is moved to be in position $\left \lceil \frac{i}{2} \right \rceil$ while the old element in that position becomes in position $\left \lceil \frac{i}{2} \right \rceil + 1$ and so on (for example, after the first search, the list becomes 1,2,3,4,9,5,6,7,8,10). The first element in the list is considered to be in position 0. Repeat part (a), using this heuristic.  \\

\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Programming question
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{[12 marks]}

In this programming question you are asked to implement both an AVL tree and a skiplist to compare the number of key
comparisons made as items are inserted, searched for and deleted.  Your implementation must follow the algorithms given
in lecture notes so the number of key comparisons will match.  Your runtimes should also match those discussed in class.
For simplicity, the key and value of an item will be int values.  Also, you do not need to consider duplicate key values
within the data structures - we will not attempt to insert a key that already exists in the data structure. \\
~\\
You may not use any pre-existing code that would trivialize the implementation (e.g. built in data structures from STL, smart pointers, etc).
You may, however, use the C++ vector data structure.  If in doubt, make a private Piazza post and ask. \\
~\\
Implement your program in C++ and provide a main function that accepts the following commands
from stdin (you may assume that all inputs are valid):

\begin{itemize}
\item[\textbullet] \texttt{i key value coin} - inserts an item $(key,value)$ into both your AVL tree and skiplist
and prints the number of key comparisons required by AVL.insert and skipList.insert, respectively, followed by a newline.
Use the value $coin$ as the number of heads flipped before a tail is reached when inserting into the skiplist. \\

\item[\textbullet] \texttt{d key} - deletes the item with the given key from both the AVL tree and skiplist and 
prints the number of key comparisons required by AVL.delete and skipList.delete, respectively, followed by a newline.
For a BST, delete should use the inorder successor (if needed).

\item[\textbullet] \texttt{savl key} - searches the AVL tree for the item with the given key and prints the corresponding
value or string \texttt{ERROR} if not found, the number of key comparisons used in the search, followed by a newline.

\item[\textbullet] \texttt{ssl key} - searches the skiplist for the item with the given key and prints the corresponding
value or string \texttt{ERROR} if not found, the number of key comparisons used in the search, followed by a newline.

\item[\textbullet] \texttt{stats} - prints 3 int values followed by a newline corresponding to: number of items in
the AVL tree/skiplist, height of the AVL tree, and total number of nodes in the skiplist (do not count $+\infty$ or $-\infty$).\\
The runtime for this operation is $\Theta(1)$ time.

\item[\textbullet] \texttt{r} - initializes an empty AVL tree and skiplist.  If a nonempty AVL tree or skiplist already exists,
they are destroyed and new empty data structures are created.

\end{itemize}
\textbf{Note}: check the sample output. There is a single space between each two values printed on the same line.\\
Place your entire program in the file \texttt{avlskip.cpp}

\end{document}