\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools,algorithm,algorithmicx,algpseudocode}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 240 Assignment 2},%
pdfsubject={University of Waterloo, CS 240, Winter 2023},%
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 2023}\\
\vspace{2mm}
{\Large\bf Assignment 2}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, February 15 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

If you are having difficulties with the assignment, course staff are there to help (provided it isn't last minute). \\
~\\
Please read
\url{https://student.cs.uwaterloo.ca/~cs240/w23/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, ... , 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{Late Policy:} Assignments are due at 5:00pm, with the grace period until 11:59pm.
Assignments submitted after 11:59 on the due date will not be accepted but may be reviewed (by request) for feedback purposes only. \\   
~\\

{\bf{Notes:}}
\begin{itemize}
\item Logarithms are in base 2, if not mentioned otherwise.
\item If you use MSD or LSD radix sort in this assignment, you are free to chose any value for radix $R$ you wish. If you chose radix $R$ other than 10 (standard decimal representation), you must account for the time it takes to transform a number in decimal representation to base $R$.
\item Array indices start from 0.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[2+2+3+3+5 = 15 marks]}
\begin{itemize}
\part{a} 
Starting with an empty max-heap, construct the heap resulting from insertion of 21, 50, 18,
4, 25, 61, 100, in that order. Show the final heap.
No explanation is necessary.
\part{b}
Let array $A=[6,2,10,9,4,11,27]$. Show the resulting array after applying heapify to $A$. 
No explanation is necessary.
\part{c}
Let $A$ be an array containing numbers in increasing order. Give an in-place algorithm that modifies $A$ so that it is a valid max-heap. Your algorithm should not perform any comparisons of elements in $A$, i.e. you cannot simply run heapify on $A$. Briefly justify your algorithm. 
%Olga

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

\part{e} 
Write an algorithm that reports the $k$ largest elements in heap $H$ in
$O(k \log{k})$ time.
You can use standard binary tree functions such as $left(v)$,  $parent(v)$, etc. for a tree node $v$.  You must provide both pseudocode and a brief description of your algorithm. Briefly justify the running time and correctness of your algorithm.

\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} $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. 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{[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} What is the best-case (i.e. the best luck) running time of $ArrayAlg$ on an array $A$ of size $n$? Justify.
	\part{b} What is the worst-case (i.e. the worst luck) running time of $ArrayAlg$ on an array $A$ of size $n$?  Justify.
	\part{c} Let $T^{exp}(n)$ be the expected running time of $ArrayAlg$ of size $n$. 
	Show how to derive a recurrence relation for $T^{exp}(n)$ and then solve it. Express $T^{exp}(n)$ using big-O asymptotic notation.  Your bound must be asymptotically tight, but
         you need not prove that it is tight.\\
\end{itemize}


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

\subsection{[4 marks]}

    You are given an array $A$ of size $n$ storing integers. Assume $A$ does not store the integer 0.
Write an algorithm $reorder(A)$ that reorders the elements of the array so that it first contains negative odd integers, then negative even integers, then positive odd integers, then positive even integers.  For example, with an initial array
$A =[ 47, 50, -78,  -76, 7, -9]$, one possible correct output is
$A = [-9, -78, -76, 47,  7, 50] $. There are other valid outputs; your algorithm needs to return any one of them.  
Your algorithm must be in-place and must run  in $O(n)$ time. 
 You must provide a detailed explanation of your algorithm in words. You can also provide pseudocode, if you wish, but it is not required.
Briefly justify correctness and the running time. 





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

\subsection{[4 marks]}

Let $sortSemiSorted(A,k)$ be an algorithm with parameters $A$, an array of size $n$ storing arbitrary numbers, and $k$,  a positive integer. Furthermore, array $A$ is such that the first $k$ numbers are sorted, the next $k$ numbers are sorted, and so on. For example, if $k=4$, then $A=[6, 9, 10, 12, 1, 2,5, 7]$ is a valid input. You can assume $n$ is divisible by $k$. Algorithm $sortSemiSorted$ sorts $A$.
Prove  $sortSemiSorted(A,k)$ must have running time $\Omega (n \log{\frac{n}{k}})$.  You can use the fact that for a positive integer $m$,  $(\frac{m}{e})^m \leq m! \leq m^m.$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[2+2+3+3 = 10 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 unexamined digits, nothing else, and no explanation is required for your answer. 

\part{c}
Explain how to sort $n$ numbers in the range $[0,n^5)$ in $O(n)$ time. 

\part{d} 
Let $A$ be an array storing non-negative integers in radix $R$. The size of $A$ is $n=R^b$ for some positive integer $b$, and the smallest number in $A$ is larger than $R^b$.
MSD sort on array $A$ examines at most $k$ digits for each number. What is the smallest value $k$ can take? In other words, what is the smallest possible height of the recursion tree of MSD sort?

\end{itemize}

\end{document}