\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, Winter 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 Winter 2025}\\
\vspace{2mm}
{\Large\bf Assignment 2}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, February 4 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/w25/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 11:59PM on February 4 will be accepted without penalty. Your last submission will be graded. Please note that submissions made after 11:59PM {\bf will not be graded} and may only be reviewed for feedback. \\  
~\\

{\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 choose any value for radix $R$. If you choose 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$.
\end{itemize}




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

\begin{itemize} 

\part{a}
Let $H$ be a max-heap of size 13 with unique elements. 
On which level(s) of the heap can the smallest item be located?
Recall that the topmost level in the heap is 0. No explanation is needed.

    \part{b}
Consider \emph{NewHeapify} algorithm below, which calls \emph{fix-down} subroutine described in lecture notes. Does this algorithm produce the max-heap order in the input array $A$? Give a proof or a counter-example.

 \begin{algorithme}
    $\alg{NewHeapify}(A)$\\
    $A$: an array  \\
    \lign $n\gets A.size()$ \\
  \lign \pc{for} $i\leftarrow$ 0 to \emph{parent(last())} \\
        \lign \> $fix$-$down(A,n,i)$ 
  \end{algorithme}

\part{c}
Consider a heap of size $n$ implemented with an array $H$. Let the $k$th ancestor of the node at index $i$ of the array be the ancestor of $i$ that is separated from $i$ by $k$ links. For example, the parent of $i$ is the first ancestor of  $i$.
Design an algorithm $isAncestor(x, H, i)$ which takes as an input heap array $H$, a valid index $i$ in the array and a value $x$. This algorithm should  return true if key $x$ is stored at $k$th ancestors of node $i$ for some $k \in \mathbb{Z}$, $k \geq 0$, and return false otherwise. 

\par In order to obtain full marks, your algorithm should be as efficient as possible. You \textbf{must} write pseudo-code for this question. In addition, as for any other algorithm you provide in assignments, you must describe the algorithm, briefly justify correctness, and analyse its running time complexity in terms of $n$. Be precise about the indices your algorithm explores. 

\par Note: For this problem, you may assume that taking a log of any number or raising $2$ to any integer power takes a constant amount of time (not true in general for our idealized computer model).  

\end{itemize}


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

\subsection{[5 marks]}
Consider the following algorithm, which takes as an input a bitstring $w$ of length $n$.
Furthermore, $w$ has exactly 3 bits equal to 1. What is the average case running time of the algorithm below?
Note that on line 6, if $count=2$, then the for loop on lines 6-7 will execute $n^{2}$ times.

 \begin{algorithme}
    $\alg{Mystery}(w)$\\
\\ $w$ is a bitstring of length $n\geq3$ containing exactly three bits equal to 1\\
     \lign    $count \gets 0$\\
     \lign \pc{for} $i =1$ \pc{to} $n-1$ \\
     \lign  \hspace{5ex} \pc{if} $w[i-1] > w[i]$\\
       \lign \hspace{10ex}$count \gets count  + 1$\\       
       \lign    $sum \gets 0$\\
      \lign    \pc{for} $i =1$ \pc{to} $n^{count}$ \\
       \lign  \hspace{5ex}  $sum \gets sum+1$\\      
\lign  \pc{return} sum\\
   \end{algorithme}



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

\subsection{[2+5=7 marks]}


Consider the algorithm below, where
\textit{random(k)} returns an integer from the set of $\{ 0, 1,  \ldots, k-1\}$ uniformly and at random.  

  \begin{algorithme}
    $ArrayAlg(A,n)$ \\
    $A$: an array storing numbers\\
    \lign  \pc{if} $n = 1$ \\
    \lign \> \pc{return}\\
     \lign $i \gets random(n) + 1$ \\
     \lign   \pc{for} $j = 1$ \pc{to} $i$ \pc{do} \\
     \lign  \>  print($A[j - 1]$) \\
     \lign    $ArrayAlg(A,n-1)$ \\
  \end{algorithme}


\begin{itemize} 	
	\part{a} Provide a tight ($\Theta$) bound for the worst-case (i.e. the worst luck) running time of $ArrayAlg$ on array $A$ of size $n$. Justify.
	\part{b} Let $T^{exp}(n)$ be the expected running time of $ArrayAlg$ for an input 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{[2+5=7 marks]}


Consider the algorithm below,  which is a variant of {\emph{QuickSort}}.
Here, subroutine {\it use-one-key-comparison} is unknown but uses
exactly one key-comparison, and algorithm {\emph{partition}} is the same algorithm as shown in class.
Now let $T^{ best}(n)$ and $T^{ worst}(n)$ be the best and worst case
number of key-comparisons performed by {\it mysteryQS} for an array of size $n$. Note that we are only counting key-comparisons performed by the sub-routine {\it use-one-key-comparison}.

\begin{algorithme}
$mysteryQS	(A,n\gets A.\alg{size})$ \\
\label{alg:mysteryQS}
\pc{if} $n>1$\\
	\>   $p \gets \alg{choose-pivot}(A)$\\
    \>   $i \gets \alg{partition}(A,p)$\\
	\>  $mysteryQS(A[0,1,\ldots,i-1])$\\
	\> $mysteryQS(A[i+1,\ldots,n-1])$\\
	\> \pc{for} $j=0$ to $i$ \pc{do}\\
	\>	\>\pc{for} $k=i$ to $n-1$ \pc{do}\\
		\>\>\>	{\emph{use-one-key-comparison()} }
\end{algorithme}


\begin{itemize}
\part{a} Show that $T^{\rm worst}(n)\in \Omega(n^2)$.
\part{b} Show that $T^{\rm best}(n)\in O(n^2 \log n)$.
\end{itemize}

Remark:   Obviously not both (a) and (b) can be tight.   To keep the assignment shorter we did \emph{not} ask you to get the tight bounds here.








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

\subsection{[5 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. 

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

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


\begin{itemize}
\part{a} 
Show the contents of array $A=[54, 121, 38, 82]$ 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. No explanation is required. 

\part{c}
Provide a $\Theta$ bound on the running time of bucket-sort when sorting an array of size $n^3$ containing elements in the range $[1,\ldots,n^{5}]$. Briefly explain.


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


\end{itemize}


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


\end{document}



    