\documentclass[12pt]{article} 

\usepackage{fullpage}
\usepackage{amsmath,amssymb}
\usepackage{color}
\usepackage{hyperref} % for the URL
\usepackage{verbatim} % for comments, for version control
\usepackage[ruled,vlined,linesnumbered,titlenumbered]{algorithm2e}
\DontPrintSemicolon
\SetKwInOut{Input}{Input}
\usepackage{tikz}   	% for drawing various pictures
\usetikzlibrary{patterns,calc,chains,shapes.multipart,arrows,positioning,shapes,automata,fit,shadows,arrows.meta,trees}


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


\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240E, Spring 2025}\\
\vspace{3mm}
{\Large\bf Written Assignment 1}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, May 20, 2025 at 5pm}, with grace period until 7:59pm\\
\end{center}

Be sure to read the assignment guidelines 
(\url{https://student.cs.uwaterloo.ca/~cs240e/s25/assignments.phtml#guidelines}).
Submit your solutions electronically to Crowdmark. Ensure you have read, signed, and
submitted the Academic Integrity Declaration AID01.

\textbf{Grace period:} submissions made before 8pm on May 20 will
be accepted without penalty. Please note that submissions made after 8pm
\textbf{will not be graded} and may only be reviewed for feedback.


%Submit your solutions electronically as a PDF on Crowdmark.


\subsection{[9 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+6=9 marks]}

Motvation:   In class we often use a sloppy recursion, or assume that
``$n$ is divisible as needed''.   The following question illustrates that, 
with some limitations,  this approach is justified.

\begin{itemize}
\part{a}  Show that the following statement is {\bf true}.

	``Let $f: \mathbb{R}^+\rightarrow \mathbb{R}^+$ be a monotonically increasing function. 
	Assume that $f(x)\leq x$ 
	whenever $x$ is a power of 2, i.e., $x=2^k$ for some integer $k\geq 0$.
	Then $f(x)\in O(x)$.''

\part{b} Show that the following statement is {\bf false}.

	``Let $f: \mathbb{R}^+\rightarrow \mathbb{R}^+$ be a monotonically increasing function. 
	Assume that $f(x)\leq x$  for infinitely many integers, i.e., for any $N$ there exists
	an integer $x\geq N$ with $f(x)\leq x$.  Then $f(x)\in O(x)$.''

	Reminder:   To show that a statement is false, you need to 
	give an example that satisfies all assumptions of the statement,
	but does not satisfy the conclusion.   
\end{itemize}



\subsection{[9 marks]}

Consider a (max-oriented) meldable heap $H$ that holds $n$ integers.  
% the "meldable" isn't important; change to "binary" if meldable is not covered
%
%\begin{enumerate}
%\item 
%
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{[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.

\noindent Your answers must work for arbitrary $d$, even if $d$ is not constant.

\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{[3+7+3=13 marks]}

How would you implement \alg{increase-key}($z,k$) 
in a binomial heap?  The method is given as parameter
a node $z$ and a key $k$ and it should increase the
key of $z$ to $k$ if it was smaller before.

\begin{enumerate}
\part{a}
\begin{minipage}[t]{50mm}
        Prof.~B.~Fuddled thinks that they can implement this using \alg{fix-up} as follows: 
\end{minipage}
\hspace*{\fill}
\begin{minipage}[t]{90mm}
\vspace*{-5mm}
\begin{algorithm}[H]
\label{alg:fixUp}
\caption{{\it increase-key}$(z,k)$}
   \If {$(k>z.{\mathit key}())$} {
      $z.\mathit{key} \gets k$\;
      \While(\tcp*[f]{do fix-up}) {$p\gets z.\mathit{parent}$ is not $\mathit{NULL}$ and $p.\mathit{key}< z.\mathit{key}$} {
         swap key-value pairs of $z$ and $p$\;
         $z \gets p$\;
      }
   }
\end{algorithm}
\end{minipage}

Show that Prof.~Fuddled is incorrect.  Thus, give an example of
a flagged tree that satisfies the binomial-heap-order
property, indicate a node $z$ and a key $k>z.key$, and show
that calling $\alg{increase-key(z,k)}$
results 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 a method to implement {\it increase-key} in a flagged tree with
	the binomial-heap-order property, with
                worst-case run-time $O(\log n)$.

\part{c} Recall that $\alg{decrease-key}(z,k)$ is given a node $z$ and a key $k$ and should decrease the key of $z$ to $k$ if it was bigger before.    Show that this operation can be reduced to the other operations.    Specifically, show that if a priority queue realization supports $\alg{size},\alg{find-max},\alg{delete-max},\alg{increase-key}$ and $\alg{insert}$ with $O(f(n))$ run-time, then you can also realize $\alg{decrease-key}$ with $O(f(n))$ run-time.

\end{enumerate}
\end{document}
