\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools,algorithm,algorithmicx,algpseudocode, soul}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 240 Assignment 2},%
pdfsubject={University of Waterloo, CS 240, Winter 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}[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 Winter 2024}\\
\vspace{2mm}
{\Large\bf Assignment 2}\\
\vspace{3mm}
\textbf{Due Date: February 13 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
Please read
\url{https://student.cs.uwaterloo.ca/~cs240/w24/assignments.phtml#guidelines} 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, ...  
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 {\bf 5:00pm}, with the grace period until 11:59pm. \\  
~\\

% {\bf{Notes:}}
% Logarithms are in base 2, if not mentioned otherwise.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[2+3+5=10 marks]}
\begin{itemize}
\part{a}
Let array $A=[6,2,10,9,4,11,27]$. Show the resulting array after applying heapify to $A$. 
No explanation is necessary.

\part{b} 
Let array $H$ of size $2^k$ store a permutation of integers in $\{1,..,2^k\}$, where $k$ is integer larger than 1. Array $H$ is also a valid max-heap. 
What is the largest key that can be stored in a leaf of the heap? Explain.

\part{c}
You are given:

\begin{itemize}
\item  Algorithm $median(A)$ which takes an array $A$ of size $n$ and returns its median element. For example, if $A=[6,1,3]$ then $median(A)$ returns 3, and if  $A=[6,2,4,5]$ then $median(A)$ returns 4. The running time is $O(n)$.
\item  Algorithm $partition(A,x)$ which takes an array $A$ of size $n$ and number $x$ and partitions $A$ in such a way that all elements smaller than $x$ are placed at smaller indexes than all elements that are larger than $x$.  For example, $[1,3,6]$ is a valid output for $partition([6,1,3],5)$  and $[1,2, 3,6]$ is a valid output for $partition([6,1,3,2],2)$.  
The running time is $O(n)$.
\end{itemize}
 Design algorithm $CS240Heap$, which given an array $A$ of size $n$ rearranges all the elements in such a way that if we view array $A$ as a min heap, $any$ key at level $i-1$ is smaller than $any$ key at level $i.$  For example, if the input array is $A=[5,3,8,1,4,2]$, one possible valid output of $CS240Heap$ is $A=[ 1, 3, 2, 5, 4, 8]$.  
The running time of $CS240Heap$ must be $O(n).$  You can assume $n=2^{k}-1$ for some integer $k$, i.e. the last level of the heap is full.
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[2+3+2+4 = 11 marks]}
\begin{itemize}
\part{a}
Let $H$ be a heap of height $h$. How many key comparisons must be performed by $deleteMax()$ in the worst case? Give the exact, not asymptotic,   answer (i.e. the answer should be a function of $h$, for example,  $2+h$, or $h^2$, as appropriate).  Describe the worst case instance where this number of comparisons is achieved.

\part{b}
Consider method  $deleteMaxFaulty(H)$, implemented as follows.
First we  remove the item at the root node and store it in a variable to be returned to the user. Then we compare the items at the two children of the root. Whichever item is larger is moved to the root. We repeat this last step at the node of the deleted item until we reach a leaf. The pseudocode for  is below. 


\begin{algorithme}
    $\alg{deleteMaxFaulty}(H)$\\
    $H$: is an array storing max heap \\
    \lign $i \gets 0$\\
    \lign $toReturn \gets H[0]$\\
     \lign \pc{while} $i$ is not a leaf \pc{do}\\
      \lign \hspace{5ex} \pc{if}  $i$ \text{has right child} \pc{and} $i$ has left child\\
      \lign \hspace{10ex}  $H[\text{right child of }  i].key > H[\text{left child of } i].key$ \\  
       \lign \hspace{15ex} $H[i] = H[\text{right child of } i].key$ \\
       \lign \hspace{15ex} $i \gets$ right child of $i$ \\
       \lign \hspace{10ex} \pc{else}\\
       \lign \hspace{15ex} $H[i] = H[\text{left child of }i].key$ \\
       \lign \hspace{15ex} $i \gets$ left child of $i$ \\
             \lign \hspace{5ex} \pc{else}  \\
       \lign \hspace{10ex} $H[i] = H[\text{left child of } i].key$ \\             
       \lign \hspace{10ex} $i \gets$ left child of $i$ \\       
    \lign  $H.size\gets H.size-1$\\   
    \lign  \pc{return} $toReturn$\\
   \end{algorithme}


Explain why  $deleteMaxFaulty()$ does not perform deletion of the maximum element correctly.

\part{c}
How many key comparisons does $deleteMaxFautly()$ perform in the  worst case? Give the exact, not asymptotic, answer.

\part{d} Develop a method $fixAfterDeleteMaxFaulty()$, s.t. if we run it after $deleteMaxFaulty()$, the result is a valid heap. The maximum number of key comparisons allowed for 
 $fixAfterDeleteMaxFaulty()$ is $\log{h}$.   You can modify $deleteMaxFaulty()$ to return more items in the output in addition to the deleted maximum element.  
You do not have to write pseudo-code, you can describe your algorithm in sufficient detail.
Note that we are {\bf{not}} asking for the runtime of  $fixAfterDeleteMaxFaulty()$  to be $O(\log{h}),$ but putting a restriction on the allowed number of key comparisons.
\end{itemize}


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


\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} $n^4$ \\
       \lign  \hspace{10ex}  $sum \gets sum+i * sum$\\
      \lign  \hspace{5ex} \pc{return} sum\\
      \lign  \pc{if} $A[0] > A[1]$  \pc{and} $A[1] > A[2]$\\
       \lign  \hspace{5ex}\pc{for} $i =1$ \pc{to} $n^3$ \\
         \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. 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 $Mystery(A)$).
\end{itemize} 




\subsection{[5 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^2$ \pc{do} \\
     \lign  \>  \st{print($A[j]$)} print($A[i])$\\
     \lign    $ArrayAlg(A[0,...,A.size-2])$ \\
  \end{algorithme}


Let $T^{exp}(n)$ be the expected running time of $ArrayAlg$ of size $n$. 
	Derive a tight recursive upper bound for $T^{exp}(n)$ and then solve it. Express your final answer using big-O asymptotic notation.  Your bound must be asymptotically tight, but you need not prove that it is tight.



\subsection{[5 marks]}         
Write an in-place partition algorithm called $ModuloPartition(A)$ that takes an
array $A$ of $n$ numbers and rearranges  $A$ in such a way that all the values that are equivalent to $0 \mod 10$ precede all
the values equivalent to $1 \mod 10$, which precede all the values equivalent to $2 \mod 10$, etc.
For example, for an input array $A = [7, 62, 5, 57, 12, 39, 5, 8, 16, 48]$, one possible correct result
is $A = [12, 62, 5, 5, 16, 57, 7, 8, 48, 39]$. The runtime of your algorithm must be $\Theta(n).$



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[5 marks]}
Given an array $A[0\ldots n-1]$ of numbers, show that if $A[i] \geq A[i-j]$
for all $j \geq \log n$ then the array can be sorted 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 think about how to apply sorting to blocks.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[2+2+2+3=9 marks]}


\begin{itemize}
\part{a} 
Show the contents of array $A=[45, 112, 83, 8]$ after one round of LSD sort, where one round means one application of single digit bucket sort. No explanation is required.

\part{b}
Perform MSD sort on array  $A=[736, 212, 213, 376, 354, 850]$. For each number, underline the digits (if any) which are not examined by MSD sort. You only need to underline the not examined digits, nothing else, and no explanation is required for your answer. 

\part{c}
What is the running time of bucket-sort when sorting an array of size $n^2$ containing elements in the range $[0,..,n^{10}]$? Briefly explain.


\part{d}
Explain how to sort $n$ integers in the range $[0,n^{100})$ in $O(n)$ time. 


\end{itemize}


\end{document}