\documentclass[12pt]{article} 

\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{color}
\usepackage{hyperref} % for the URL
\usepackage{verbatim} % for comments, for version control
\usepackage{ifthen} % for version control
\usepackage[ruled,vlined,linesnumbered]{algorithm2e} % for algorithms
\usepackage{todonotes}
\usepackage{tikz}   	% for drawing various pictures
\usetikzlibrary{patterns,calc,chains,shapes.multipart,arrows,positioning,shapes,automata,fit,shadows,arrows.meta,trees}
\usepackage[normalem]{ulem} % for sout


%%%%%% other possibly useful things
\def\part#1{\item[\bf #1)]}
\renewcommand{\thesubsection}{Question \arabic{subsection}}


\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240E, Winter 2021}\\
\vspace{3mm}
{\Large\bf Assignment 1}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, January 27, 2021 at 5pm} \\
\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 (AID) before you start working on the assessment and
submit it \textbf{before the deadline of January 27} along with your answers to the 
assignment; i.e. \textbf{read, sign and submit A01-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{http://www.student.cs.uwaterloo.ca/~cs240e/w21/guidelines/guidelines.pdf} for guidelines on submission.  
\textbf{Each written question solution must be submitted individually to MarkUs as a PDF} with the corresponding file names: 
a1q1.pdf, a1q2.pdf, ... , a1q6.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{Remember, late assignments will not be marked but can be submitted to MarkUs after the deadline for feedback if you email cs240e@uwaterloo.ca and let the ISAs know to look for it. (\#3).} \\

For all questions, you may use facts from calculus, but review briefly
the name of the fact and exactly what it is stating.  (Refer to how the 
notes review concavity or l'H\^{o}pital's rule for examples.)

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

Dr. I.~M.~Smart has invented a new class of functions, denoted $O'(f)$: A function $f(n)$ is in $O'(g(n))$ if there is a constant $c>0$ such that $f(n)\le cg(n)$ for all $n> 0$.    

% can omit this, since listed earlier
%To prove a
%statement, you should provide a formal proof that is based on the
%definitions of the order notations.  To disprove a statement, you can
%either provide a counter example and explain it or provide a formal proof.
All functions map positive integers to positive integers.
\begin{enumerate}
\part{a} Prove that $f(n)\in O'(g(n))$ implies that $f(n)\in O(g(n))$.

\part{b} Prove that $f(n)\in O(g(n))$ implies that $f(n)\in O'(g(n))$.

\end{enumerate}

\subsection{[7{\color{red}(+2)} marks]}

Consider the following (rather strange) code-fragment:

\begin{verbatim}
mystery (int n) {
// pre: n >= 2
    compute L := floor( log (n) ) 
    if L is even print all subsets of {1,...,L}
    else print all subsets of {1,...,2L}
}
\end{verbatim}

For example, for $n=17$, we have $L=\lfloor \log(17) \rfloor = 4$, so
the code prints all $16$ subsets of $\{1,2,3,4\}$.

Let $f(n)$ be the run-time of this code.  You may assume that computing
$\log(n)$ takes $\Theta(1)$ time, and printing the subsets of $\{1,\dots,k\}$
takes $\Theta(2^k)$ time.

\sout{Show that cannot exist a constant $d$ such that $f(n)\in \Theta(n^2)$.}

{\color{red}
Show that $f(n)\not \in \Theta(n^2)$.

\smallskip
Bonus: Show that cannot exist a constant $d$ such that $f(n)\in \Theta(n^d)$.}

\subsection{[2+6+4=12 marks]}

To reduce the height of the heap 
one could use a $d$-way heap.  This is a tree where each node 
contains up to $d$ children, all except the bottommost level are
completely filled, and the bottommost level is filled from the left.
It also satisfies that parents are bigger than all their children.

\begin{enumerate}
\part{a} Explain how to store a $d$-way heap in an array $A$ of size $O(n)$
	such that the root is at $A[0]$.
	Also state how you find parents and children of the node stored
	at $A[i]$.  You need not justify your answer.

\part{b} What is the height of a $d$-ary heap on $n$ nodes? 
	Give a tight asymptotic bound that depends on $d$ and $n$.
	You may assume that $n$ and $d$ sufficiently big (e.g. $d\geq 3$
	and $n\geq 10$).

\part{c} 
Assume that $n\geq 4$ is a perfect square.  
	What is the height of a $d$-ary heap for $d=\sqrt{n}$?  
	Give an exact bound (i.e., not asymptotic).

\end{enumerate}

\subsection{[3+7=10 marks]}

\newcommand{\alg}[1]{\ensuremath{\text{\it #1}}}

How would you implement \alg{increaseKey}($v,k$) 
in a binomial heap?  The method is given as parameter
a node $v$ and the new value $k$ that its key should
have.  

\begin{enumerate}
        \part{a}
        Prof. Dodo thinks he can implement this using \alg{fix-up} as follows:

\begin{algorithm}[ht]
\caption{{\it increaseKey}$(v,k)$}
   \If {$(k>v.{\mathit key}())$} {
      $v.\mathit{key} \gets k$\;
      \tcp{perform fix-up}
      \While {$p\gets v.\mathit{parent}$ is not $\mathit{NIL}$ and $p.\mathit{key}< v.\mathit{key}$} {
         swap key-value pairs of $v$ and $p$\;
         $v \gets p$\;
      }
   }
\end{algorithm}

                Show that Prof.~Dodo is incorrect.  Thus, give an example of
                a flagged tree that satisfies the binomial-heap-order
                property, indicate a node $v$ and a key $k>v.key$, and show
                that calling \verb+increaseKey(v,k)+ with the above code would
                result in a flagged tree that does not satisfy the
                binomial-heap-order property.  (Try to keep your tree small,
		no more than 16 nodes. )

\begin{minipage}{0.75\linewidth}
The tree on the right is drawn here so that you
can see (in the published \LaTeX-file) how
one can easily draw a tree using {\tt tikz}.
You don't have to draw your tree with {\tt tikz},
but are encouraged to do so.
\end{minipage}
\begin{minipage}{0.2\linewidth}
\begin{tikzpicture}[scale=0.7,every node/.style={circle,draw,minimum width=2em},
	level 1/.style={sibling distance = 60pt},
	level 2/.style={sibling distance = 80pt},
	level 3/.style={sibling distance = 40pt}]
\node {$a$}
	child { node {$b$}
		child { node {$c$} 
			child { node {$d$} }
			child { node {$e$} }
		}
		child { node {$f$} 
			child { node {$g$} }
			child { node {$h$} }
		}
	}
	child { edge from parent[draw = none] }
;
\end{tikzpicture}
\end{minipage}

\part{b} Give an implementation of {\it increaseKey} in a binomial heap
                that has worst-case run-time $O(\log n)$. 

\end{enumerate}

\subsection{[1+1+2(+5) = 4(+5)  marks]}

Consider the following pseudo-code, which is a variant of \alg{quick-sort}:

\SetKwInOut{Input}{Input}
\begin{algorithm}[ht]
	\caption{$\alg{mysteryQS}	(A,n\gets A.\alg{size}$) }
\Input{array $A$ of size at least $n$}
\uIf{$n>1$}{
	$p \gets \alg{choose-pivot}(A)$\; 
	$i \gets \alg{partition}(A,p)$\;
	$\alg{mysteryQS}(A[0,1,\ldots,i-1])$\;
	$\alg{mysteryQS}(A[i+1,\ldots,n-1])$\;
	\For{$j=1$ to $i$} {
		\For{$k=i+1$ to $n-1$} {
			\alg{mystery($A,j,k$)} \tcp*{This uses one key-comparison} 
		}
	}
}
	\ElseIf{$n=1$}{ 
		$\alg{mystery}(A,0,0)$\;
		}
\end{algorithm}

Here \alg{choose-pivot} always returns $n-1$, and \alg{partition} is Hoare's
partition-routine and uses $n$ key-comparisons.
Let $T^\alpha(n)$ be the number of key-comparisons used by \alg{mysteryQS} 
(for various scenarios $\alpha$).  You may assume that $n$ is divisible
as needed (i.e., ignore rounding issues).

\begin{itemize}
\part{a} State the recursive formula for $T^{\alpha}(n)$ if we know
	the pivot-index $i$.  No explanation needed.
\part{b} Show that $T^{\rm worst}(n)\in \Omega(n^2)$.
\part{c} Show that $T^{\rm best}(n)\in O(n^2 \log n)$.
\part{d} (Bonus) Give asymptotically tight bounds for $T^{\rm worst}(n)$ and $T^{\rm best}(n)$. Doing this question will also give you the credit for (b) and (c).
\end{itemize}

Hint: Study the function $f(x)=x(n-x)$.  Where is its minimum and maximum?

\end{document}
