\documentclass[12pt]{article}

\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools,algorithm,algorithmicx,algpseudocode, float}
\usetikzlibrary{shapes,positioning,calc,chains}
\usepackage[pdftitle={CS 240 Assignment 3},%
pdfsubject={University of Waterloo, CS 240,Spring 2022},%
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{\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}
}

% \snode{ID}{NUMBER} becomes \node{ID}[item]{\ensuremath{NUMBER}}
\newcommand{\snode}[2]{\node(#1)[item]{\ensuremath{#2}}}

% \nodelabel{SUBSCRIPT} becomes \node[label]{\ensuremath{S_SUBSCRIPT}}
\newcommand{\nodelabel}[1]{\node[label]{\ensuremath{S_#1}}}

\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}}

\renewcommand{\thesubsection}{Problem \arabic{subsection}}
\definecolor{typo}{rgb}{0.75,0,0}
\definecolor{care}{rgb}{0,0,0}

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 Spring 2022}\\
\vspace{2mm}
{\Large\bf Assignment 3}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, June 15 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 15} along with your answers to the assignment; i.e. \textbf{read, sign and submit A03-AID.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{https://student.cs.uwaterloo.ca/~cs240/s22/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, a3q3.pdf, a3q4.pdf, a3q5.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 on Wednesday.  Students are allowed to submit \textbf{one} late assignment, 2 days after the due date on Friday by 5:00pm.  
Assignments submitted after Friday at 5:00pm or Wednesday at 5:00pm (if you have already used your one late submission) will not be accepted for grading but may be reviewed (by request) for feedback purposes only. If you want to use your one time late assignment allowance, please send an email to ``cs240@uwaterloo.ca'' with the title ``Using one time late assignment allowance''.\\  
%Note: you may assume all logarithms are base 2 logarithms:  $\log = \log_2$.
%%%%%%%%%%   Q1


\subsection{[5 marks]}
Derive the average-case run time of the algorithm $HalfSort(A)$. Your derivation must be based on the definition of the average-case running time (not on an equivalence of running time to some randomized version of $HalfSort(A)$).  You can assume $n$ is divisible by 2 in your analysis. Express  running time asymptotically. 
You can use the fact that $\sum_{n=0}^{\infty}{ \frac{n}{2^n}}=c$ for some constant $c$.

\begin{algorithme}
	$\alg{HalfSort}(A)$\\
	$A$: an array of size $n\geq 2$ storing distinct numbers\\
	\lign    $i \gets 1$\\
	\lign \pc{while} $i < n $ \\
	\lign  \hspace{5ex} \pc{if} $A[i-1] > A[i]$\\
	\lign \hspace{10ex} \pc{return} false\\
	\lign  \hspace{5ex}  $i \gets i+2$\\
	\lign  \pc{return} true\\
\end{algorithme}



\subsection{[2+2+4=8 marks]}


Consider the algorithm below, where
\textit{random(k)} returns an integer from the set of $\{ 0, 1, 2, \ldots, k-1\}$ uniformly and at random.  

\begin{algorithme}
	$ArrayAlg(A)$ \\
	$A$: an array storing numbers\\
	\lign  \pc{if} $A.size == 1$ \\
	\lign \> \pc{return}\\
	\lign $i \gets random(A.size)$ \\
	\lign   \pc{for} $j = 0$ \pc{to} $i$ \pc{do} \\
	\lign  \>  print($A[j]$) \\
	\lign    $ArrayAlg(A[0,...,A.size-2])$ \\
\end{algorithme}


\begin{itemize} 
	\part{a} What is the best-case (i.e. the best luck) running time of $ArrayAlg$ on array $A$ of size $n$? Justify.
	\part{b} What is the worst-case (i.e. the worst luck) running time of $ArrayAlg$ on array $A$ of size $n$?  Justify.
	\part{c} Let $T^{exp}(n)$ be the expected running time of $ArrayAlg$ of size $n$. 
	Show how to derive a recurrence relation for $T^{exp}(n)$ and then solve it. Express $T^{exp}(n)$ using big-O asymptotic notation.  Your bound must be asymptotically tight, but
	you need not prove that it is tight.\\
\end{itemize}


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

\subsection{[0 + 3 + 3 + 3 = 9 marks]} 

Work with an AVL tree: 
\begin{enumerate}
	\part{a} \textbf{Practice }(not worth any marks): Starting with an empty AVL tree, insert the following
	keys in order: 42 5 12 14 23 56 57 59 64.
	You should obtain the AVL tree given in the next part.
	
	\part{b}  Given the following AVL tree:
	Note: this tree shows balance factors instead of height.
	\begin{center}
		\begin{tikzpicture}[
			every node/.style = {draw, shape = circle split, grow = down},
			level 1/.style={sibling distance=100 pt},
			level 2/.style={sibling distance=50pt}]
			\node(z){$23$\nodepart{lower}$+1$}
			child{node{12\nodepart{lower}$0$}
				child{node {5\nodepart{lower}$0$}}
				child{node {14\nodepart{lower}$0$}}
			}
			child{
				node{56\nodepart{lower}$+1$}
				child{node {42\nodepart{lower}$0$}}
				child{node {59\nodepart{lower}$0$}
				      child{node {57\nodepart{lower}$0$}}
			          child{node {64\nodepart{lower}$0$}}}
			};
		\end{tikzpicture}
	\end{center}
	
	Insert the following keys in order: 58$\star$, 16, 15, 22$\star$.
	Show the resulting AVL trees with balance factors (not height) for each node after
	the elements marked with star ($\star$) are inserted.
	
	Note: you should only show 2 trees.	
	
	\part{c} Consider all the nodes in the tree we get at the end of part (b). Suppose we start with an empty tree. What is an ordering for inserting the nodes into the tree that does not cause any rotations? \textbf{Write} your example, then \textbf{propose }a general idea of creating such orderings and \textbf{justify} your answer.
	
	\part{d} Delete the following keys in order: 23$\star$, 12, 14, 5$\star$.\\
	Show the resulting AVL trees with \textbf{balance factors} (not height) for each node after
	the elements marked with star ($\star$) are deleted. If you have a choice of which element
	to move up, pick the inorder successor.
	
	Note: you should only show 2 trees.
\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.\\

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


\subsection{[0 + 3 + 3 + 3 + 3 = 12  marks]}

\begin{enumerate}
	\part{a} Practice (not worth any marks): Starting with an empty skip list, insert the following keys in order: 18 12 33 25 14 20 using the following coin flip sequence:
	
	\begin{center}
		THHTTHHHTHTTHT
	\end{center}
	
	You should obtain the skip list given in the next part.
	
	\part{b} Given the following skip list:
	
	\begin{center}
		\begin{tikzpicture}[
			start chain,
			every node/.style={font=\small},
			item/.style={rectangle,minimum height=6mm,minimum width=10mm,
				rounded corners=2mm,thick,draw=black},
			label/.style={rectangle,minimum size=6mm}
			]
			
			% The nodes of the skip list are drawn in a matrix
			% \\ delimits the rows while & delimits the columns
			\matrix[row sep=3mm, column sep=5mm]{
				% Row 4: -infty ... +infty
				\nodelabel{4}; & \snode{4a}{-\infty}; & & & & & & & \snode{4n}{+\infty};\\
				
				% Row 3: -infty             25 +infty
				\nodelabel{3}; & \snode{3a}{-\infty}; & & & & & \snode{3j}{25};  & & \snode{3n}{+\infty};\\
				
				% Row 2: -infty 12          25    +infty
				\nodelabel{2}; & \snode{2a}{-\infty}; & \snode{2c}{12}; & &	& & \snode{2j}{25}; & & \snode{2n}{+\infty};\\
				
				% Row 1: -infty 12  14      25    +infty
				\nodelabel{1}; & \snode{1a}{-\infty}; & \snode{1c}{12}; & \snode{1e}{14};& & & \snode{1j}{25};  & & \snode{1n}{+\infty};\\
				
				% Row 0: -infty 12 14 18 29 25 33 +infty
				\nodelabel{0}; & \snode{0a}{-\infty}; & \snode{0c}{12};  & \snode{0e}{14}; & \snode{0f}{18}; 
				& \snode{0h}{20};  & \snode{0j}{25};  & \snode{0l}{33};  & \snode{0n}{+\infty};\\
			};
			
			% Start chaining the nodes together
			{
				% Horizontal chains
				% Specify a starting node (by ID), and join to other nodes (by going "through" them in an unbroken line)
				% Eg row 2: Start at 2a, join 2e, join 2h, join 2i
				[start chain] \chainin(0a); \chainin(0c) [join]; \chainin(0e) [join]; \chainin(0f) [join]; \chainin(0h) [join];
				\chainin(0j) [join]; \chainin(0l) [join]; \chainin(0n) [join];
				[start chain] \chainin(1a); \chainin(1c) [join]; \chainin(1e) [join]; \chainin(1e) [join]; \chainin(1j) [join];\chainin(1n) [join];
				[start chain] \chainin(2a); \chainin(2c) [join]; \chainin(2j) [join]; \chainin(2n) [join];
				[start chain] \chainin(3a); \chainin(3j) [join]; \chainin(3n) [join];
				[start chain] \chainin(4a); \chainin(4n) [join];
			}
			{
				% Vertical chains
				% Need to be separate chains from the horizontal ones
				[start chain] \chainin(0a); \chainin(1a) [join]; \chainin(2a) [join]; \chainin(3a) [join]; \chainin(4a) [join]; 
				[start chain] \chainin(0c); \chainin(1c) [join]; \chainin(2c) [join];
				[start chain] \chainin(0e); \chainin(1e) [join]; 
				[start chain] \chainin(0j); \chainin(1j) [join]; \chainin(2j) [join]; \chainin(3j) [join];
				[start chain] \chainin(0n); \chainin(1n) [join]; \chainin(2n) [join]; \chainin(3n) [join]; \chainin(4n) [join]; 
				
			}
		\end{tikzpicture}
	\end{center}
	
	
	Show the skip list that is created by inserting the keys: 28, 42, 8, 1, 22, 99 \\
	into the given skip list.  You must use the following coin flip sequence:
	\[
	THTTHHHHTTTTHTTHT
	\]
	Note that each coin flip in the sequence will only be used once, in order
	and there may be some unused coin flips.
	
	After inserting all keys, determine the exact number of comparisons (between 2 keys) required to 
	search for the keys inserted in this part (that is, indicate what the search cost would be
	for 28, and then the search cost for 42, and so on).
	
	For example, a search for 18 in the given skip list above (from Part (a)), requires 6 comparisons.
	
	\begin{center}
		\begin{tabular}{|c||c|c|c|c|c|c|} \hline
			Key &  28 &  42 &  8 &  1 & 22 & 99 \\ \hline
			Comparisons &  &  &   &   &   &   \\ \hline
		\end{tabular}
	\end{center}
	
	For the remaining parts, assume that the probability of adding a level to a tower is $p$ ($0 < p < 1)$, as opposed to $\frac{1}{2}$.
	
	\part{c} Explain why the probability that a tower in the skip list with height at least $i$ is $p^i$.
	
	\part{d} Show that the expected number of extra nodes (i.e., the total number of nodes in skip list not including the nodes in $S_0$)  is $O(n)$. 
	Therefore, the space requirements for this skip list are linear in the number of keys being stored. 
	
	\part{e} Show that the expected height of a skip list is at most $\log_{1/p}(n) + 1/(1-p)$. \\
	Remember to also consider the left and right sentinels.\\
	To make the math a bit easier, you may assume $n$ is a power of $1/p$.
	
\end{enumerate}


\end{document}
