
\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 240 Assignment 1},%
pdfsubject={University of Waterloo, CS 240, Winter 2022},%
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{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\renewcommand{\thesubsection}{Question \arabic{subsection}}
\usepackage{enumitem}

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 Spring 2022}\\
\vspace{2mm}
{\Large\bf Assignment 2}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, June 1 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

The integrity of the grade you receive in this course is very important to you and the University of Waterloo.  
As part of every assessment in this course you must read and sign an Academic Integrity Declaration before you start working on the assessment and submit it \textbf{before the deadline of June 1} along with your answers to the assignment; i.e. \textbf{read, sign and submit A02-AID.txt now or as soon as possible}.
The agreement will indicate what you must do to ensure the integrity of your grade.
If you are having difficulties with the assignment, course staff are there to help (provided it isn't last minute). \\
~\\
\textbf{The Academic Integrity Declaration must be signed and submitted on time or the
assessment will not be marked.} \\
~\\
Please read
\url{https://student.cs.uwaterloo.ca/~cs240/s22/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, a2q3.pdf, a2q4.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 on Wednesday.  Students are allowed to submit \textbf{one} late assignment, 2 days after the due date on Friday by 5:00pm.  
Assignments submitted after Friday at 5:00pm or Wednesday at 5:00pm (if you have already used your one late submission) will not be accepted for grading but may be reviewed (by request) for feedback purposes only. If you want to use your one time late assignment allowance, please send an email to ``cs240@uwaterloo.ca'' with the title ``Using one time late assignment allowance''.\\  
~\\
%Note: you may assume all logarithms are base 2 logarithms:  $\log = \log_2$.
%%%%%%%%%%   Q1


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

\subsection{[4 marks]}

Suppose we are working with a 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 of this element in the array. Describe an
algorithm that performs this task and analyse its complexity (since we
did not prove correctness of fix-up/fix-down in class, we do
not require you to prove correctness).

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

\subsection{[8 marks]}

We want to prove the following: there is no comparison-based algorithm
that can merge $m$ sorted arrays of length $m$ into a unique sorted
array of length $m^2$ doing $O(m^2)$ comparisons. We argue by
contradiction, and we assume that it is possible, so that we have such
an algorithm (which we call FastMerge).

Modify MergeSort in order to use FastMerge, and derive a
contradiction. You may use the following property: if a function
$T(n)$ satisfies $T(n) = \sqrt{n} T(\sqrt{n}) + O(n)$, then $T(n) =
O(n \log(\log(n)))$. Do not worry about $n$ being a perfect square or
not.

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

\subsection{[8 marks]}

Given an array $A[0\ldots n-1]$ of numbers, show that if $A[i] \geq
A[i-j]$ for all $j \geq \log(n)$, the array can be sorted in $O(n \log(\log(n)))$ time.

\smallskip
\noindent \textit{Hint:} Partition $A$ into contiguous blocks of size
$\log (n)$; i.e.  the first $\log (n)$ elements are in the first
block, the next $\log (n)$ elements are in the second block, and so
on. Then, establish a connection between the elements within two
blocks that are separated by another block.

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

\subsection{[3+3+4 marks]}

The {\em median} of a sequence $(a_1,\dots,a_n)$ of integers is
defined as follows: assume we sort these integers, and write them as
$(a'_1,\dots,a'_n)$ once sorted. Then their median is $a'_{\lceil n/2
  \rceil}$. For instance:
\begin{itemize}
\item if $n=1$, the median of $(2)$ is $2$
\item if $n=2$, the median of $(5,1)$ is $1$
\item if $n=3$, the median of $(2,10,1)$ is $2$ 
\item if $n=4$, the median of $(5,5,2,1)$ is $2$, etc
\end{itemize}
Even though we sort the sequence to {\em define} the median, it is
possible to avoid using any sorting algorithm to {\em compute} it: for
instance, quickselect finds the median of a sequence of length $n$ in
average time $O(n)$.

In this problem, we study an {\em online} algorithm for finding the
median of a sequence: we suppose that we receive the entries of the
sequence one at a time, and we want to print the medians of all these 
partial sequences as we go. For instance:
\begin{itemize}
\item suppose we first receive ${\bf 15}$. We print ${\bf 15}$, which is the median of 
  the sequence $(15)$
\item next, we receive ${\bf 10}$. We print ${\bf 10}$, which is the median of 
  the sequence $(15,10)$
\item next, we receive ${\bf 1}$. We print ${\bf 10}$, which is the median of 
  the sequence $(15,10,1)$
\item next, we receive ${\bf 20}$. We print ${\bf 10}$, which is the median of 
  the sequence $(15,10,1,20)$
\item next, we receive ${\bf 30}$. We print ${\bf 15}$, which is the median of 
  the sequence $(15,10,1,20,30)$
\end{itemize}

Re-computing the median from scratch every time would be too slow.
Here is an idea for a better algorithm: use two heaps $H_{\rm lo}$ and
$H_{\rm hi}$, each of which will roughly contain half of the elements
seen so far: if we have seen $n$ elements, $H_{\rm lo}$ should contain
the $\lceil n/2 \rceil$ smallest elements, $H_{\rm hi}$ should contain
the $\lfloor n/2 \rfloor$ largest ones.

\begin{enumerate}[label=(\alph*)]
\item On the example $(15,10,\dots)$ above, show us what these heaps would contain
at each of the 5 steps (we don't know if these are min-heaps or
max-heaps yet, so just tell us what elements they contain).
\item 
We would like to be able to read off the (current) median using just one
access to $H_{\rm lo}$. What kind of heap should it be, a min-heap or a max-heap?
How long does finding the current median take?
\item 
Describe how to update the two heaps when inserting the next element.
In particular, in which heap do you insert the element, and how do you
ensure that $H_{\rm lo}$ and $H_{\rm hi}$ have the required size
afterwards? Give the runtime of your update method, with a short
justification; it should be $o(n)$. (At this stage, you will have to explain whether
$H_{\rm hi}$ should be a min-heap or a max-heap.)


\end{enumerate}

\end{document}
