\documentclass[12pt]{article}

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


\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 Spring 2025}\\
\vspace{2mm}
{\Large\bf Assignment 3}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, June 17 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
Read
\url{https://student.cs.uwaterloo.ca/~cs240/s25/assignments.phtml#guidelines} for guidelines on submission.  
\textbf{Each question must be submitted individually to Crowdmark.} 
Submit early and often.\\
~\\
\textbf{Grace period:} submissions made before 19:59PM on June 17 will be accepted without penalty. Your last submission will be graded. Please note that submissions made after 19:59PM {\bf will not be graded} and may only be reviewed for feedback. \\  
~\\



\begin{enumerate}
\item {[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. The following
recurrence relation may show up: $T (n) = \sqrt{n}T (\sqrt{n}) + O(n)$; here you can disregard issues
related to the fact that $\sqrt{n}$ is not necessarily an integer. You can use the fact that this gives $T (n) \in
o(n \log n)$ \textbf{without proving it.}




\item {[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. You may assume that the numbers are given in
base $n$, and that computing $x \mod n$ and computing floor are constant time operations. each number is given as a word on memory. So, you don't have direct access to digits of a given number.




\item {[2+5+5=12 marks]}
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 {55}
    child {node {46}
      child {node {13}
        child {node {7}}
        child {node {42}
          child {node {17}}
          child {node {45}}
        }
      }
      child {node {49}
        child {edge from parent[draw=none]}
        child {node {51}}
      }
    }
    child {node {82}
      child {node {59}}
      child {node {92}
        child {node {89}}
        child {edge from parent[draw=none]}
      }
    }
  ;
\end{tikzpicture}\end{center}
\caption{Binary tree $T$ of problem 1 \label{tree}}
\end{figure}
\begin{enumerate}
\item Show that the tree $T$ in Figure~\ref{tree}
is an AVL tree by writing in the balance factor in the lower half of each node.


\item  Show the process of inserting a KVP with key 29 into the tree
$T$ in Figure~\ref{tree}.
  Specifically, draw the tree, with balance factors, after each call to
 {\sf restructure}.


 
\item
   Show the process of deleting key 49 from the \emph{original} tree $T$
in Figure~\ref{tree}. 
  Specifically, draw the tree, with balance factors, after each call to {\sf
 restructure}.



 
\end{enumerate}





\item {[2+6+5=13 marks]}

Consider an AVL tree $T$ with $n$ nodes, and let $v$ be a leaf in $T$. We
want to give a lower bound on the {\em depth} $\ell$ of $v$, that is,
the length of the path from the root of $T$ to $v$.
\begin{enumerate}
\item Let $v_0,\dots,v_\ell$ be the path from the root of $T$ to $v$ 
  (where $v_0$ is the root of $T$ and $v_\ell=v$), and let $T_0,\dots,T_\ell$
  be the subtrees of $T$ rooted at respectively $v_0,\dots,v_\ell$. 
  What is $T_0$ and what is $T_\ell$?


\item Prove by  induction that for $i=0,\dots,\ell$, $T_{\ell-i}$
  has height at most $2i$.


\item Using the previous question, deduce a lower bound of the form
  $\ell \in \Omega(g(n))$, for a certain function $g(n)$.


\end{enumerate}


\item {[6 marks]}
Describe an algorithm for computing the height of a given AVL tree (where nodes store the balance factor $\{-1,0,1\}$ instead of height)
in $O(\log n)$ time on an AVL tree of size $n$.  In the pseudocode, use
the following terminology:
{\sf T.left}, {\sf T.right}, and {\sf T.parent} indicate the left
child, right child, and parent of a node $T$ and {\sf T.balance}
indicates its {\it balance factor} (-1, 0, or 1).  For example if
$T$ is the root we have {\sf T.parent=nil} and if $T$ is a leaf we
have {\sf T.left} and {\sf T.right} equal to {\sf nil}.  The input
is the root of the AVL tree.  Justify correctness of the algorithm
and provide a brief justification of the runtime.




















\end{enumerate}


















\end{document}