\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 2025},% 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 2026}\\ \vspace{2mm} {\Large\bf Assignment 2}\\ \vspace{3mm} \textbf{Due Date: Tuesday June 9, 5pm} \end{center} Please read the following link for guidelines on submission: \begin{center} \url{https://student.cs.uwaterloo.ca/~cs240/assignments.phtml#guidelines} \end{center} \textbf{Late Policy:} Assignments are due at 5:00pm, with a grace period until 7:59pm. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{[1+4+5 marks]} We want to design a variant of MergeSort that divides the array $A$ into $k$ subarrays rather than two, with the division taking place at indices $n/k$, $2n/k$, \dots, $(k-1)n/k$. Here, $k$ is a fixed constant, which we will take of the form $k=2^s$ ($s$ integer), to simplify some calculations. In this problem, {\em we only count comparisons between elements in our arrays}, and {\em we give upper bounds on the worst-case runtime}. We will deviate slightly from the asymptotic point of view that hides constants: we want to understand the impact of the choice of $k$, so you will have to give explicit inequalities, not big-Os. \begin{enumerate}[label=(\alph*)] \item With $k=2$, show that you can merge two sorted arrays $A_1$ and $A_2$ into a single sorted array $A$ using at most $n$ element comparisons, if we assume that $A_1$ and $A_2$ both have length $n/2$ (you can assume $n$ even). \item More generally, for $k$ of the form $k=2^s$, show that you can merge $k$ sorted arrays $A_1,\dots,A_k$ into a single sorted array $A$ using at most $ns = n \log_2(k)$ element comparisons, if we assume that $A_1,\dots,A_k$ all have length $n/k$ (you can assume $n$ is a multiple of $k$). \item Give the variant of MergeSort that subdivides the input array into $k$ subarrays, and give an explicit (not asymptotic) upper bound on the number of element comparisons it does. You can assume that $n$ is a power of $k$. \end{enumerate} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{[1+3+4+5 marks]} We want to implement a {\em double-ended priority queue}. This is a collection where we can insert elements, access the minimum or maximum and remove the minimum or maximum; our goal is do to insert, delete-min, delete-max in worst-case time $O(\log(n))$ (if there are $n$ elements in the collection) and find-min, find-max in constant time. To support these requirements, we use two heaps $H_1$ (a min-heap) and $H_2$ (a max-heap) stored as arrays. At all times, these heaps should contain the same set of elements, but stored in a different order. You should also use two arrays $T_1$ and $T_2$ that specify the correspondence between the elements of $H_1$ and $H_2$: $T_1[i]$ gives the index of $H_1[i]$ in $H_2$, and conversely $T_2[i]$ gives the index of $H_2[i]$ in $H_1$. \begin{enumerate}[label=(\alph*)] \item Explain how to implement find-min and find-max, and justify the runtime. \item Give an algorithm to update the arrays $T_1$ and $T_2$ if we swap the elements of indices $i$ and $j$ in $H_1$ (we do not worry whether swapping these two elements breaks the heap condition in $H_1$). Give (and justify) the cost of this operation, and a brief justification of its correctness. \item Give an algorithm to insert a new key in the data structure. Give (and justify) the worst-case cost of this operation, and a brief justification of correctness. Big-Os are sufficient. \item Give algorithms to do delete-min and delete-max. Give (and justify) the worst-case cost of these operations, and a brief justification of correctness. Big-Os are sufficient. \end{enumerate} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{[2+4+5 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 only count how many times we call ${\tt test}$ at step 3 of the algorithm. \begin{enumerate}[label=(\alph*)] \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? What about $j > n-s$? \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} \noindent {\bf The following exercises are provided for additional practice and are not part of the graded portion of the assignment. While these questions will not be evaluated, we strongly encourage you, and expect you, to work through them to deepen your understanding of the material. You are welcome to upload your solutions to Crowdmark for your own record-keeping and organization; however, no grades or feedback will be provided for these submissions. You may also ask questions about these exercises during office hours or on Piazza.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{} 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{} 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 worst-case complexity in terms of the number $n$ of elements in the heap (give a big-O), and briefly justify correctness (you can take for granted that the algorithms for insert and delete in a heap are correct without reproving them, of course). Note: if your algorithm runs in time $\Omega(n)$ in the worst case, you will not receive full marks. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{} Let $A$ be an array of $n$ distinct integers. An {\em inversion} is a pair of indices $(i,j)$ such that $i A[j]$. \begin{enumerate}[label=(\alph*)] \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$. Hint: indicator variables indexed by $i,j$. \item Give the average runtime of insertion sort (as a Theta bound), assuming that in size $n$ you run it over all $n!$ permutations of $1,\dots,n$. \end{enumerate} \end{document}