\documentclass[12pt]{article}

\usepackage{algo,tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools,enumitem}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 240 Assignment 1},%
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}}

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 Spring 2021}\\
\vspace{2mm}
{\Large\bf Assignment 2}\\
\vspace{3mm}
\textbf{Due: Wednesday, June 9 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 9th} along with your answers to the 
assignment; i.e. \textbf{read, sign and submit A02-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: 
a2q1.pdf, a2q2.pdf, ... , a2q6.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{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$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[4 + 6 = 10 marks]}
Consider a heap implemented with an array. Let the $k$th ancestor of node at index $i$ of the array be the ancestor of $i$ that is separated from $i$ by $k$ edges. For example, the parent of $i$ is the 1st ancestor of  $i$.
\begin{enumerate} [label=\alph*)]
\item 
 Prove by induction that the $k$th ancestor of node at index $i$, if present, is stored at index $\floor{\frac{i+1}{2^{k}} - 1 }$. You can use the following equality without a proof:
if $n,m$ are integers, and $n$ is a positive integer, then for a real  number $x$,
$$ \floor{\frac{x-m}{n}} = \floor{ \frac{ \floor{x}-m}{n}  }. $$
\item
Suppose we have a max-heap  implemented with an array $H$ and storing $n$ keys.
Design an algorithm $isAncestor(x, H, i)$ which takes as an input heap array $H$, a valid index $i$ in the array and $x$. This algorithm should  return true if key $x$ is stored at one of the ancestors of node $i$, false otherwise. The running time of your algorithm should be $O(\log{\log{n}}).$
You can use the result from part (a) even if you did not do part (a). You can assume that you have values of $2^k$ for $1 \leq k \leq \log{n}$ pre-computed, so that  computation of $2^k$ takes only $O(1)$ time. 
\end{enumerate}


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

\subsection{[3+3+5+4=15 Marks]}




One potential pitfall of $QuickSort$ is that it does not necessarily perform 
well if there are many repeated elements.

\begin{enumerate} [label=\alph*)]
\item 
Assume that you call $QuickSort$ on an array of size $n$
    where all elements are the same.   Derive (with an explanation) an  asymptotically tight bound
    on the run-time, presuming you 
    always use the simple partition-algorithm, listed below.

\begin{algorithme}
$partition(A, p)$ \\
$A$: array of size $n$,\quad $p$: integer s.t. $0\leq p<n$ \\
\> Create empty lists \textit{small},  \textit{equal}, and \textit{large}. \\
\> $v\gets A[p]$ \\
\> \pc{for} each element $x$ in $A$ \\
\>\> \pc{if} $x < v$ append $x$ to \textit{small} \\
\>\> \pc{else} \pc{if} $x > v$ append $x$ to \textit{large} \\
\>\> \pc{else} append $x$ to \textit{equal} \\
\> $i\gets \mathit{size}(\mathit{small})$ \\
\> $j\gets \mathit{size}(\mathit{equal})$ \\
\> Overwrite $A[0\ldots i{-}1]$ by elements in \textit{small} \\
\> Overwrite $A[i\ldots i+j{-}1]$ by elements in \textit{equal} \\
\> Overwrite $A[i{+}j\ldots n{-}1]$ by elements in \textit{large} \\
\> return $i$
%}}
\end{algorithme}


\item 
Assume that you call $QuickSort$ on an array of size $n$
    where all elements are the same.   Derive (with an explanation) an  asymptotically tight bound
    on the run-time, presuming you 
    use Hoare's partition-algorithm from class (listed below).

  \begin{algorithme}
    $partition(A, p)$\\
    $A$: array of size $n$,\quad $p$: integer s.t. $0\leq p<n$ \\
    \lign $\mathit{swap}(A[n-1],A[p])$ \\
    \lign $i \gets -1,\quad j \gets n-1, \quad v \gets A[n-1]$ \\
    \lign \pc{loop} \\
    \lign \> \pc{do} $i \gets i+1$ \pc{while}  $A[i] < v$\\
    \lign \> \pc{do} $j \gets j-1$ \pc{while} $j\geq i$ and $A[j] > v$\\
    \lign \> \pc{if} $i \ge j$ \pc{then} \pc{break}  {\quad(goto 9)}\\
    \lign \> \pc{else} $\mathit{swap}(A[i],A[j])$ \\
    \lign \pc{end loop} \\
    \lign $\mathit{swap}(A[n-1],A[i])$ \\
    \lign \pc{return} $i$
  \end{algorithme}

  
\item  One possible improvement to $QuickSort$ is to modify 
    $partition$
    so that it returns three subsets:  The left part has items $<v$, the
    middle part has items $=v$, and the right part has items $>v$.
    Describe how to modify Hoare's algorithm to achieve this.
    In particular, fill in the pseudo-code (and explain it)
    for the following stub:

\begin{algorithme}
         $ThreeWayPartition(A,p)$\\
         $A$: array of size $n$,  $p$: integer s.t. $0\leq p<n$\\
     \lign $v\leftarrow A[p]$ \\
     \lign ... \\
         \lign return($i,j$) \\
    \lign // $A[0..i{-}1]$ has items $<v$, $A[i..j]$ has items $=v$, $A[j{+}1..n{-}1]$ has items $>v$ 
\end{algorithme}
\iffalse
\fbox{\parbox{\linewidth}{
\begin{algorithmic}
    \State\emph{ ThreeWayPartition($A$,$p$)}
    \State{ Input  $A$: an array of size $n$,  $p$: integer s.t. $0\leq p<n$}
    \State {\hspace{2ex}  $v\gets A[p]$}
    \State{\hspace{2ex} ... }
    \State{\hspace{2ex}return(i,j)}
    \State{// $A[0..i{-}1]$ has items $<v$, $A[i..j]$ has items $=v$, $A[j{+}1..n{-}1]$ has items $>v$ }
\end{algorithmic}     
}
}    
\fi

Your algorithm must have worst-case run-time $O(n)$ and    be {\em in-place}, i.e., use $O(1)$ additional space. 


\item Describe how $ThreeWayPartition$ can be useful for 
$QuickSort$ when repeated elements are allowed.   In particular,
what modifications would you make to the following pseudo-code from class?  

  \begin{algorithme}
    $QuickSort1(A)$ \\
    $A$: array of size $n$ \\
    \lign \pc{if} $n \leq 1$ \pc{then return}\\
    \lign $p \gets choosePivot1(A)$ \\
    \lign $i \gets partition(A,p)$ \\
    \lign $QuickSort1(A[0,1,\ldots,i-1])$ \\
    \lign $QuickSort1(A[i+1,\ldots,n-1])$
  \end{algorithme}


Your modifications should be such that if the input array has $k$
distinct elements, then the {\em worst-case} run-time of the algorithm
is $O(kn)$.  Argue that this holds.

\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{[8 marks]}
A student designed a data structure and named it an {\tt almost-priority-queue}.  This data structure allows two operations: {\tt insert} and
 {\tt extract\_almost\_Max}, where  {\tt extract\_almost\_Max} outputs either the largest priority or the second largest priority item. Also, {\tt extract\_almost\_Max}  does not tell you whether it extracted the largest or second largest priority item.
 In case the data structure has only one element,  {\tt extract\_almost\_Max} extracts that element.
 The student claims that the worst case running time of both {\tt insert} and  {\tt extract\_almost\_Max}
is $o(\log n)$. Prove that the student has made a mistake in the running time analysis of their data structure. 
 \\
 {\em Hint:} Sorting takes $\Omega(n\log n)$ time.






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


\subsection{[3+3+5=11 marks]}

Consider the algorithm below, where
\textit{random(n)} returns an integer from the set of $\{ 0, 1, 2, \ldots, n-1\}$ uniformly and at random.  Array $A$ stores non-repeating integers in the range  $\{ 0, 1, 2, \ldots, n-1\}$ . 


  \begin{algorithme}
    $ArrayAlg(A, n, k)$ \\
    $A$: array of size $n$ \\
     \lign $i \gets random(n)$ \\
    \lign \pc{if} $A[i] == k$ \pc{then return} $i$\\
     \lign \pc{else} \\
     \lign \>  \pc{for} $j = 0$ \pc{to} $n$ \pc{do} \\
     \lign \> \>  print(`*') \\
     \lign \>   $ArrayAlg(A, n, k)$ \\
  \end{algorithme}

\begin{enumerate} [label=\alph*)]
	\item What is the best-case running time of $ArrayAlg$? 
	\item What is the worst-case running time of $ArrayAlg$? 
	\item Let $T(n)$ be the expected running time of $ArrayAlg$. 
	Write a recurrence relation for $T(n)$ and then solve it.  Express your answer using $\Theta$ notation. \\
\end{enumerate}

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

\subsection{[6 marks]}
Let $R_1,\dots,R_n$ be $n$ axis-aligned rectangles in the plane
for which the corners are points in the $n\times n$-grid.
Thus, for each rectangle $R_i$ the four corners are points
where both coordinates are integers in $\{1,\dots,n\}$. Degenerate rectangles (i.e. rectangles of height or width zero) are allowed.
Give an algorithm to sort $R_1,\dots,R_n$ by increasing area
in $O(n)$ time.



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

\subsection{[6 marks]}
Let $A$ be an array of size $n$ storing numbers $0, 1$. It is known that the array starts with $0$ ends with $0$, and that all $1$'s are consecutive. A valid example is $A=[0,1,1,1,0,0]$. Give an exact  (not asymptotic) lower bound on the number of comparisons required to find the smallest index $i$ and largest index $j$ s.t.  $A[i]=1$ and $A[j]=1.$ You can assume that $n\geq 3.$



\end{document}