\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 1},%
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 2026}\\
\vspace{2mm}
{\Large\bf Assignment 3}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, June 30 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 Read
\url{https://student.cs.uwaterloo.ca/~cs240/s26/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 30 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. \\  
~\\
\textbf{Reminder:} all logarithms are in base 2 unless stated otherwise.



%%%%%%%% Q1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{[1+1+5 =7 marks]}
Consider the following algorithm.

 \begin{algorithme}
    $\alg{Mystery}(A)$\\
    $A$: an array of size $n\geq 2$ storing distinct numbers\\
     \lign    $sum \gets 0$\\
     \lign    $sorted \gets true$\\
     \lign \pc{for} $i =1$ \pc{to} $n-1$ \\
     \lign  \hspace{5ex} \pc{if} $A[i-1] > A[i]$\\
       \lign \hspace{10ex}$sorted \gets false$\\
      \lign  \pc{if} $sorted$\\
      \lign  \hspace{5ex}  \pc{for} $i =1$ \pc{to} $2^n$ \\
       \lign  \hspace{10ex}  $sum \gets sum+i * sum$\\
      \lign  \hspace{5ex} \pc{return} sum\\
      \lign  \pc{if} $A[0] > A[1]$\\
       \lign  \hspace{5ex}\pc{for} $i =1$ \pc{to} $n^2$ \\
         \lign  \hspace{10ex}  $sum \gets sum+i*sum$\\
\lign  \hspace{5ex} \pc{return} sum\\
\lign  \pc{return} sum\\
   \end{algorithme}

\begin{itemize}
\part{a} What is the best-case running time? Use $\Theta$ notation. Briefly justify.
\part{b} What is the worst-case running time? Use $\Theta$ notation. Briefly justify.

\part{c} Derive the average-case running time.
Use $\Theta$ notation. 



\end{itemize} 




%%%%%% Q2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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} For an array $A$ of size $n$, what is the fastest possible execution of $ArrayAlg(A)$? Justify.

	\part{b} For an array $A$ of size $n$, what is the slowest possible execution of $ArrayAlg(A)$? Justify. 

	\part{c} Let $T^{exp}(n)$ be the expected running time of $ArrayAlg$ an input of size $n$. Give a tight asymptotic bound for $T^{exp}(n)$. Justify your answer.
	\\

\end{itemize}




%%%%%%%% Q3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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}[(\roman*)]
\item each node stores the height of the subtree rooted at it.
\item Every key in $A$ is less than every key in $B$.
\item $h_A=h_B -1$ 
\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.

\part{b}
Describe an algorithm \texttt{Join2}$(T_A, T_B, h_A, h_B)$ as in part a), except that assumption (iii) is replaced by the following:
\begin{enumerate}
\item[(iii)] $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}



%%%%%%%% Exercises %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\noindent {\bf The following exercises are provided for additional practice and are not part of the graded portion of the assignment. While these questions will not be 
evaluated, we strongly encourage you, and expect you, to work through 
them to deepen your understanding of the material. You are welcome to 
upload your solutions to Crowdmark for your own record-keeping and 
organization; however, no grades or feedback will be provided for these 
submissions. You may also ask questions about these exercises during 
office hours or on Piazza.}

%%%%%%%% Q4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{} 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.}


%%%%%%%% Q5 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{}
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.

%%%%%%%% Q6 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\subsection{}

We consider biased skiplists, where Heads come up with probability $p
\in (0,1)$, and Tails with probability $1-p$. You can assume that the
number of keys $n$ is $n=1/p^K$ for some integer $K$.

\begin{enumerate}
\item[(a)] Give an upper bound on the expected height of a biased skiplist
  (give a explicit inequality, not a big-O). Your upper bound should
  look like $g(n,p) + h(p)$, for some rather simple functions $g,h$ and when
  $p=1/2$, your answer should be similar to the one seen in class.
\end{enumerate}
To analyze the expected cost of search, we are going to consider search paths
backward (so either going left or going up at each step).
\begin{enumerate}
\item[(b)] Justify the following observation: if we follow a search path backward,
  then whenever we can go up, we must go up.
\item[(c)] Fix a level $i \ge 0$, let $-\infty < k_1 < \cdots <k_m <
  \infty$ be the keys at that level and consider the search path going
  backward from some $k_j$. For $j =0,\dots,m$, call $E_j$ the expected number of
  left-steps the path does before going up.

  Give a recurrence relation for $E_j$, and use it to derive a closed
  form expression for it. Alternative: you may get the closed form expression
  directly, without using a recurrence, if you favor a more brute-force kind of approach.
  
\item[(d)] Give an upper bound $E_j \le f(p)$, for some very simple function $f(p)$
\end{enumerate}
Let us use $P=\sum_{i = 0}^{{\rm expected~height}-1} (f(p) +1)$ as a proxy for
the expected cost of search, where the $+1$ accounts for the steps
up.
\begin{enumerate}
\item[(e)] At this stage, you can write $P \le A(n,p) + B(p)$, for
  some simple functions $A,B$. For a given $n$, what value of $p$
  minimizes the term $A(n,p)$?
\end{enumerate}

\paragraph{Formulas you can use}
\begin{itemize}
\item if $S_0=0$ and $S_{j+1} = a S_j + b$, $a \ne 1$, then $S_j = b \frac{1-a^j}{1-a}$
\item $\sum_{j=0}^{N-1} j a^j= \frac{a - N a^N + (N-1)a^{N+1}}{{1-a}^2}$ for $a \ne 1$
\item $\sum_{i=0}^N i^2 = N(N+1)(2N+1)/6$.
\end{itemize}







\end{document}