\documentclass[12pt]{article} 

%%%%%%% a few packages.  Most of them are not actually needed for the questons 
% here, but future assignments may use them
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{color}
\usepackage{hyperref} % for the URL
\usepackage{pst-tree} % for the trees, outdated but a few questions need it
\usepackage{verbatim} % for comments, for version control
\usepackage{ifthen}
\usepackage[ruled,vlined,linesnumbered,titlenumbered]{algorithm2e}
\DontPrintSemicolon
\SetKwInOut{Input}{Input}
\usepackage{todonotes}
\usepackage{tikz}   	% for drawing various pictures
\usetikzlibrary{patterns,calc,chains,shapes.multipart,arrows,positioning,shapes,automata,fit,shadows,arrows.meta,trees}


%%%%%% for pst-tree, define a node that ALWAYS has the same width (here "99")
\newlength{\nodeLength}
\newcommand{\Node}{A}
\newcommand{\setnode}[1]{ \settowidth{\nodeLength}{#1}
  \renewcommand{\Node}[1]{ \Tcircle{\makebox[\nodeLength]{##1}} }
}
\setnode{99}

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


\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240E, Winter 2022}\\
\vspace{3mm}
{\Large\bf Written Assignment 1}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, January 19, 2022 at 5pm} \\
\end{center}

Be sure to read the assignment guidelines 
(\url{http://www.student.cs.uwaterloo.ca/~cs240e/w22/guidelines.pdf}).
Submit your solutions electronically as a PDF with file name a1sol.pdf using MarkUs. 
We will also accept individual question files named a1q1.pdf, a1q2.pdf, \dots if you wish to submit questions as you complete them.


\addtocounter{subsection}{-1}
\subsection{Academic Integrity Declaration}

Read, sign and submit A01-AID.txt now or as soon as possible.    Failure to do so
will result in 0 marks on the entire assignment.

\subsection{[5 marks]}
There are two different definitions of `little-omega' in the literature  (to distinguish
them, we will call them $\omega_0$ and $\omega_1$ here).  Fix two functions $f(x),g(x)$.
We say that
\begin{itemize}
\item \emph{$f(x)\in \omega_0(g(x))$} if for all $c>0$ there exists $n_0>0$ such that
	$|f(x)|\geq c|g(x)|$ for all $x\geq n_0$, and
\item \emph{$f(x)\in \omega_1(g(x))$} if $g(x)\in o(f(x))$.
\end{itemize}

Show that these two definitions are equivalent, i.e., $f(x)\in \omega_0(g(x))$ if and
only if $f(x)\in \omega_1(g(x))$.  Your proof must be from first principle, i.e.,
directly using the definitions (do not use the limit-rule).  Note that $f(x),g(x)$
are not necessarily positive.

\subsection{[3+3+8=14 marks]}
Consider the following (rather strange) code-fragment:

\begin{algorithm}
\caption{mystery (int $n$)} 
\Input{$n\geq 2$}
    $L \gets \lfloor \log( \log(n)) \rfloor $\;
    print all subsets of $\{1,\dots,2^L\}$
\end{algorithm}

For example, for $n=17$, we have $\log 17\approx 4.08$ and $\log(4.08)
\approx 2.02$, so $\log\log(17)\approx 2.02$ and $L=2$ (and we print
the 16 subsets of $\{1,\dots,4\}$). This question is really
asking about the run-time of {\tt mystery}, but to avoid having to deal
with constants,
define $f(n)$ to be the number of subsets that we are printing when 
calling {\tt mystery} with parameter $n$.  

\begin{enumerate}
\item[(a)] Show that $f(n)\in O(n)$.
\item[(b)] Show that $f(n)\in \Omega(\sqrt{n})$.
\item[(c)]	Prof.~Conn Fused thinks that $f(n)\in \Theta(n^d)$ for some 
constant $d$.  (By the previous two parts, necessarily $\tfrac{1}{2}\leq d
\leq 1$.)  Show that Prof.~Fused is wrong, or in other words, for any
$\tfrac{1}{2}\leq d \leq 1$ we have $f(n)\not\in \Theta(n^d)$.
\end{enumerate}

\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 the key at a parent is no smaller than the keys at all its 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$ are sufficiently big (e.g. $d\geq 3$
	and $n\geq 10$).  Note that $d$ is not necessarily a constant.

\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{[9 marks]}
Consider a (max-oriented) meldable heap $H$ that holds $n$ integers. Describe an algorithm that is
given $H$ and an integer $x$, and that finds all items in $H$ for which the priority is at least $x$.
(Note that $x$ may or may not be in $H$.)
Your algorithm should have $O(1+s)$ worst-case run-time, where $s$ is the number
of items that were found. 

\subsection{[3+7(+5)=10(+5) marks]}
How would you implement \alg{increaseKey}($v,k$) 
in a binomial heap?  The method is given two parameters:
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 shown in Algorithm~\ref{alg:fixUp}). 

\begin{algorithm}[ht]
\label{alg:fixUp}
\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 \alg{increaseKey}($v,k$) with the code in Algorithm~\ref{alg:fixUp} 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. )

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

\part{c} (Bonus) Give an implementation of {\it decreaseKey} in a binomial heap, and state a tight run-time bound.  Make your implementation as efficient as you can (the amount of bonus-marks given will depend on the asymptotic bound that you achieve).

\end{enumerate}
\end{document}
