
\documentclass[12pt]{article}
\usepackage{tikz,fullpage,url,amssymb,epsfig,color,xspace}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 240 Assignment 3},%
pdfsubject={University of Waterloo, CS 240, Spring 2024},%
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}{ }
\renewcommand{\thesubsection}{Problem \arabic{subsection}}

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 Spring 2024}\\
\vspace{2mm}
{\Large\bf Assignment 3}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, June 18 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

\noindent Please read the following link for guidelines on submission:
\vspace{-2mm}
\begin{center}
\url{https://student.cs.uwaterloo.ca/~cs240/w24/assignments.phtml#guidelines}
\end{center}

\vspace{-1mm}
\noindent \textbf{Each question must be submitted individually to
MarkUs as a PDF} with the corresponding file names: 
\texttt{a3q1.pdf}, \texttt{a3q2.pdf}, $\ldots$. 
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.

\vspace{2mm}
\noindent \textbf{Late Policy}: Assignments are due at \textbf{5:00pm}, with the grace period until 11:59pm.

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

%%% Problem 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[6 marks]}
Generalize $quick$-$select$ (Module 3 - Slide 13) to work on two input arrays. 
Let the resulting algorithm be called $quick$-$select$-$2arrays(A,B,k)$.
Arrays $A$ and $B$ are of size $n$ and $m$, respectively, and $k\in \{ 0,1,...,n+m-1 \}$. 
Algorithm $quick$-$select$-$2arrays(A,B,k)$ should return the item that would be in $C[k]$ if $C$ was the array  resulting from merging arrays $A$ and $B$  and $C$ was sorted in non-decreasing order.


Your algorithm $quick$-$select$-$2arrays(A,B,k)$ must be in-place, i.e. only $O(1)$ auxiliary space is allowed per recursive function call.
Briefly and informally  (one or two sentences) argue that the time complexity of your algorithm is the same as of $quick$-$select$, i.e., $O(v)$ in the average case where $v$ is the total number of elements in $A$ and $B$,  i.e., $v=n+m$. \\
Hint: use the same pivot-value for partitioning both arrays.  

%%% Problem 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[2+3+3=8]}
A clever student (let's call him Max) thinks he can avoid the worst-case behaviour of $quick$-$sort$ by employing the following pivot-selection procedure.
First, compute the mean $\bar{M}$ of the elements in the array.
Then choose as the pivot the element $x$ of the array, such that $|x - \bar{M}|$ is minimized, i.e., pick the element closest to the average value in the array. 
Everything else is the same as $quick$-$sort$. 
He calls the modified $quick$-$sort$ algorithm $MX$-$sort$.

\begin{itemize}
\part{a} Write down the recurrence for running time $T(n)$ of $MX$-$sort$. 
In doing so, assume $x$ is placed at index $i$ of the partitioned array.
The recurrence relation may be expressed in terms of $n$ and $i$.
	
\part{b} Assume that the elements of the array form an arithmetic sequence (i.e., have the form $a$, $a + k$, $a + 2k$, $a + 3k$, \ldots, $a + (n - 1)k)$, scrambled in some order. 
Show that, under this distribution of array elements, $MX$-$sort$ always runs in $\Theta(n \log n)$ time.

\part{c} Unfortunately, Max's scheme is not as clever as it looks. 
Give an example of an array where $MX$-$sort$ achieves its worst case runtime of $\Theta(n^2)$ and briefly explain why this example requires this time.

\end{itemize}

%%% Problem 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[8 marks]}
Given an array $A[0\ldots n-1]$ of numbers, such that $A[i] \geq A[i-j]$ for all $0 \leq i \leq n-1$ and $\log n \leq j \leq i$, design an algorithm to sort $A$ in $O(n \log \log n)$ time. \\

\noindent {\emph{Hint:}} Partition $A$ into contiguous blocks of size $(\log n)$; i.e. the first $(\log n)$ elements are in the first block, the next $(\log n)$ elements are in the second block, and so on.  
Then, establish a connection between the elements within two blocks, which are separated by another block. 

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

Consider the problem of finding the location of a given item $k$ in an array of $n$ distinct integers.  
The following randomized algorithm selects a random index and checks whether its entry is the desired value. 
If it is, it returns the index; otherwise, it recursively calls itself. 

Recall that {\textit{random(n)}} returns an integer from the set of $\{ 0, 1, 2, \ldots, n-1\}$ uniformly and at random.

\begin{verbatim}
find-index(A,n,k)
   i = random(n)
   if A[i] = k then
      return i
   else
      return find-index(A,n,k)
   end if
\end{verbatim}

\noindent In your answers below, be as precise as possible. 
You may use order notation when appropriate. 
Briefly justify your answers.
\begin{itemize}
	\part{a} What is the \textbf{best-case} running time of {\texttt{find-index}}? 
	\part{b} What is the \textbf{worst-case} running time of {\texttt{find-index}}? 
	\part{c} Let $T(n)$ be the expected running time of {\texttt{find-index}}. \\
	Write a recurrence relation for $T(n)$ and then solve it. \\
\end{itemize} 

%%% Problem 5 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[0+2+2=4 marks]}

\begin{enumerate}
\part{a} {\bf Practice} (not worth any marks):  Starting with an empty AVL tree, insert the following keys in order: 27 99 17 28 42 16 1 2 4. \\

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){$27$\nodepart{lower}$-1$}
  child{node{16\nodepart{lower}$-1$}
  	child{node {2\nodepart{lower}$0$}
  		child {node {1\nodepart{lower}$0$}}
  		child {node {4\nodepart{lower}$0$}}}
	child{node {17\nodepart{lower}$0$}}
  }
  child{
    node{42\nodepart{lower}$0$}
    	child{node {28\nodepart{lower}$0$}}
    	child{node {99\nodepart{lower}$0$}}
    };
\end{tikzpicture}
\end{center}

Insert the following keys in order:  8$^\star$, 22, 21, 18$^\star$.

Show the resulting AVL trees with {\bf 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 the following AVL tree:
\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=50pt}]
\node(z){$42$\nodepart{lower}$?$}
	child{node{22\nodepart{lower}$?$}
		child {node {13\nodepart{lower}$?$}}
		child {node {27\nodepart{lower}$?$}
			child[missing]
			child {node {28\nodepart{lower}$?$}}}}
	child {node {66\nodepart{lower}$?$}
  		child {node {56\nodepart{lower}$?$}
  			child {node {48\nodepart{lower}$?$}
  				child[missing]
  				child {node {50\nodepart{lower}$?$}}}
  			child {node {60\nodepart{lower}$?$}}}
		child {node{77\nodepart{lower}$?$}
			child{node {72\nodepart{lower}$?$}}
			child{node {99\nodepart{lower}$?$}}}}
;
\end{tikzpicture}
\end{center}

Given the above tree, delete the following keys in order:

\begin{center}
66, 13$^\star$, 72, 77, 56$^\star$, 42$^\star$ 
\end{center}

Show the resulting AVL trees with {\bf 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 3 trees.

\end{enumerate}

%%% Problem 6 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{AVL Trees [4+6 marks]}

In this question, we want to modify an AVL tree to support an operation {\tt ithSuccessor}, in addition to the standard operations {\tt insert, delete, find}.
The operation {\tt ithSuccessor} has two parameters, $x$ and $i \ge 0$, and returns the $i$th inorder successor of the node $x$.
If $i = 0$, then the node $x$ itself is returned.
You may assume that all input is valid; i.e. the successor exists (but may not be in the subtree rooted at $x$).

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}

\part{a} Give an algorithm {\tt ithNode(x, i)} which returns the $i$th inorder node in the subtree rooted at $x$.
For example, suppose the subtree contains $m$ nodes, when $i=1$, the minimum element in the subtree is returned and when $i=m$ the maximum element in the subtree is returned.
You may assume that the subtree has at least $i$ elements.
Your algorithm should take worst-case $O(\log(m))$ time.
Briefly justify that your algorithm achieves this runtime.

\part{b} Give the algorithm for {\tt ithSuccessor(x, i)} if $n$ is the number of nodes in the given AVL tree.  
Your algorithm should take worst-case $O(\log(n))$ time and must use {\tt ithNode(x, i)} from above.
Briefly justify that your algorithm achieves this runtime.

\end{enumerate}

\end{document}