\documentclass[12pt]{article}
\usepackage{fullpage,url,amssymb,epsfig,color,xspace,tikz,amsmath}
\usepackage[pdftitle={CS 240 Assignment 2},
pdfsubject={University of Waterloo, CS 240, Fall 2026},
pdfauthor={Arne Storjohann}]{hyperref}
\usepackage{graphicx}
\renewcommand{\thesubsection}{Problem \arabic{subsection}}
\begin{document}
\vspace*{-2cm}
\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 - Fall 2026}\\
\vspace{2mm}
{\Large\bf Assignment 2}\\
\vspace{3mm}
\textbf{Due Date: Tuesday October 6 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
Please follow the guidelines for submission on the course webpage.\\

\url{https://student.cs.uwaterloo.ca/~cs240/f26/assignments.phtml#guidelines}\\

\noindent
There are 51 possible marks available.
The assignment will be marked out of 49.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[5+5+5=15  marks]}
For this question, it is sufficient to provide the drawings requested.
\begin{enumerate}
\part{a} Starting with an empty heap, construct the heap resulting from insertion of 31, 40, 58, 34, 25, 43, 10.
Show the heap, drawn as a binary tree, after the insertion of 40, after insertion of 34, and after insertion of 10.
\part{b}  Let $A = \left [ \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \end{array} \right ]$.
Draw the heap, in binary tree form, after $A$ is heapified in-place using fix-downs according to the recipe in Module 2.
\part{c} Consider a heap of size $n > 15$ that is stored as an array $A$ and contains the priorities $A = \left [ \begin{array}{ccccc} -1 & -2 & -3 & \ldots & -n \end{array} \right ]$.
Perform two {\tt deleteMax} operations, and show the first three levels of the resulting heap, drawn as a binary tree, after each operation.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[10 marks]}
Let $A[0 \ldots n-1]$ be a random permutation of $n$ distinct integers.
Let $P(n)$ be the probability that $A$ is a max-heap, that is, that
the heap-order property is satisfied.
Derive the value of $P(n)$ for each of the first eight sizes $n=1,2,3,\ldots,8$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[10 marks]}
Suppose we are given an array $A[0 \ldots n-1]$ whose elements consist
of (key, value) pairs, with each 
integer key in the range $0 \ldots n - 1$ occurring
exactly once. You can access the key of a element, but not the
value, ie, \verb'A[i].key' is allowed, but \verb'A[i].value' is not
available.  The following algorithm sorts $A$ into
ascending order of its keys.
\begin{verbatim}
initialize a temporary array B[0..n-1]
for i = 0 to n-1 
   B[A[i].key] := A[i]
A[0..n-1] := B[0..n-1]
\end{verbatim}
Unlike the code above, a sorting algorithm is said to sort
\emph{in-place} if only a constant number of elements of the input
are ever stored outside the array.  Allowing non-comparison-based
algorithms, give an $O(n)$ in-place algorithm to sort $A$.  Analyze
the running time of your method.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[4+6=10 marks]}
A \emph{deterministic} algorithm is one whose execution depends
only on the input. By contrast, the execution of a \emph{randomized}
algorithm depends also on some randomly-chosen numbers. A \emph{Las
Vegas} randomized algorithm always produces the correct answer, but
has a running time which depends on the random numbers chosen
(randomized quick-select and quick-sort are of this type). Informally,
such algorithms are always correct, and probably fast. A \emph{Monte
Carlo} randomized algorithm has running time independent of the
random numbers chosen, but may produce an incorrect answer. Informally,
such algorithms are always fast, and probably correct.

\noindent
Given an array $A$ of length $n$, an element $x$ is said to be \emph{dominant}
in $A$ if $x$ occurs at least $\lfloor n/2 \rfloor + 1$ times in $A$.
That is, copies of $x$ occupy more than half of the array.
\begin{enumerate}
\part{a} Given an array $A$ that contains a dominant element,
describe an in-place Monte Carlo randomized algorithm to find the dominant
element.
Show that your algorithm has running time in $O(1)$ and returns the correct answer with probability at least 1/2.
\part{b} Given an array $A$ that contains a dominant element, describe
an in-place Las Vegas randomized algorithm to find the dominant
element. Show that your algorithm always returns the correct answer,
and has expected running time in $O(n)$.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[6 marks]}
You are given an array $A[0 \ldots n-1]$ of integers (not necessarily
distinct) that forms a max-heap of size $n$.
Describe an algorithm that takes as input an integer $c$,
not necessarily in the heap, and reports all integers in the heap
that are greater than or equal to $c$.
The running time of your
algorithm should be in $O(1+k)$, where $k$ is the number of integers
reported. Provide a brief explanation for why the running time of
your algorithm is in $O(1+k)$.
\end{document}