\documentclass[12pt]{article}

\usepackage{fullpage,amssymb}
\usepackage{enumitem}
\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, Spring 2023},%
pdfauthor={MP}]{hyperref}


\newlength{\nodeLength}
\renewcommand{\thesubsection}{Problem \arabic{subsection}}
\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 - Spring 2024}\\
\vspace{2mm}
{\Large\bf Assignment 2}\\
\vspace{3mm}
\textbf{Due Date: Tuesday June 4, 5pm}
\end{center}
Please read the following link for guidelines on submission:
\begin{center}
\url{https://student.cs.uwaterloo.ca/~cs240/s24/assignments.phtml#guidelines}  
\end{center}
\textbf{Each question must be submitted individually to MarkUs as a PDF} with the corresponding file names: 
a2q1.pdf, a2q2.pdf, \dots 
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.

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

\subsection{[4 marks]}

Starting with an empty heap, show the max-heap resulting from
insertion of 20, 4, 200, 100, 0, 50 (show the heap, drawn as a binary
tree, after the last {\tt insert} operation).  Then, perform three {\tt
  deleteMax} operations, and show the heap, drawn as a binary tree,
after each operation.

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

\subsection{[4 marks]}

A \emph{stable} sorting algorithm is one in which the relative order
of all identical entries is the same in the output as it was in the
input.  Suppose for instance that we sort pairs of keys / values
$(k,v)$, using only the key $k$ for comparisons, and that objects
$(k,v),(k,v')$ with identical keys are allowed to show up; then, if
$(k,v)$ comes before $(k,v')$ in the input, it should come before
$(k,v')$ in the output.

Is heapsort, as seen in class, a stable sorting algorithm?  If
so, prove it; if not, give a counter-example.

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

\subsection{[2 marks]}

You are given a positive integer $n$ of the form $n=2^h-1$, for some
integer $h\ge 1$.  Give an example of an array of length $n$ where the
first method of building a max-heap seen in class (using fix-ups) uses
$\Omega(n \log(n))$ element comparisons. Give a brief justification.

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

\subsection{[5 marks]}

Suppose we are working with a max heap, represented as an array, and
we want to remove an element from it that is not necessarily the root.
We are given the index $i$ of this element in the array. Describe an
algorithm that performs this task, give the pseudo-code, analyse its
complexity in terms of the number $n$ of elements in the heap, and
briefly justify correctness.  Note: if your algorithm runs in time
$\Omega(n)$ in the worst case, you will not receive full marks.

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

\subsection{[2+4+5 = 11 marks]}

Consider $n$ distinct keys $k_0,\dots,k_{n-1}$ stored in an array $A$
of length $n$, with array indices ranging from $0$ to $n-1$. We
consider the problem of finding the first key in $A$ that satisfies a
certain condition ${\tt test}(k)$, using the following algorithm:

\medskip

\noindent {{\bf find}$(A)$}
\begin{algorithmic}[1]
\State $n = {\rm length}(A)$
  \For {${i=0,\dots,n-1}$}
  \If {${\tt test}(A[i])$}  \label{comp}
  \State \Return $A[i]$
  \EndIf
\EndFor
\State \Return ``not found''
\end{algorithmic}

\medskip

\noindent 
In the questions below, we are interested in the {\em average} cost of
this procedure, where the average is taken over the $n!$
permutations $\sigma$ of $\{0,\dots,n-1\}$. For the cost analyses, we
count only how many times we call ${\tt test}$ at step 3 of the
algorithm.
\begin{enumerate}
\item Suppose that no key in the array satisfies ${\tt test}$. What is
  the average number of tests we do? Give the exact number (and
  justify your answer).
  
\item Suppose now that there are exactly $s \le n$ keys in $A$ that
  satisfy ${\tt test}$.
  For $j$ in $\{0,\dots,n-s\}$, prove that there are exactly 
  $$ {{n-s} \choose j } j! s (n-j-1)!$$ permutations $\sigma$ of
  $\{0,\dots,n-1\}$ for which in the corresponding array $A$,
  \begin{itemize}
  \item ${\tt test}(A[0]),\dots,{\tt test}(A[j-1])$ are all false
  \item ${\tt test}(A[j])$ is true
  \end{itemize}
  How many tests do we do for these permutations?

  Prove that for $j > n-s$, there are no such permutations.

\item Still under the assumption of the previous question, give the
  average number of key comparisons we do, in terms of $n$ and $s$ (we
  want the exact value).  We recommend you use the following equalities
$$\sum_{j=0}^{n-s} (j+1) {{n-j-1} \choose {s-1}} = \sum_{j=0}^{n-s}
 (j+1) \frac{(n-j-1)!}{(n-j-s)!(s-1)!}  = {{n+1} \choose {s+1}},$$
  which you don't have to prove (the first one is trivial, the second
  one not so much). You can do this questions without completing the
  previous one.
\end{enumerate}

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

\subsection{[3+2+2+4 = 11 marks]}

Let $A$ be an array of $n$ distinct integers. An {\em inversion} is a
pair of indices $(i,j)$ such that $i<j$ and $A[i] > A[j]$.
\begin{enumerate}
\item Determine the maximum number and minimum number
 of inversions in an array of $n$ distinct
  integers. Explain what the arrays that attain these maxima and
  minima look like.
\item Given a pair of distinct indices $(i,j)$, determine the number
  of permutations for which $(i,j)$ is an inversion (do not just give
  the number; we want a justification).
\item Determine the average number of inversions in an array of $n$
  distinct integers. The average is computed over all $n!$
  permutations of the $n$ integers in $A$.
\item Suppose a sorting algorithm is only allowed to exchange {\em
  adjacent} elements $(i,i+1)$. Show that its worst-case and
  average-case complexity is $\Omega (n^2)$; you should use some
  results of the previous parts in your proof. Can you name such an
  algorithm?
  
  Hint: what happens to the number of inversions when you perform
  such an exchange?
\end{enumerate}

\end{document}
