\documentclass[12pt]{article} 

%%%%%%% a few packages (not all of which are necessarily needed)
\usepackage{fullpage}
\usepackage{amsmath,amssymb}
\usepackage{color}
\usepackage{hyperref} % for the URL
\usepackage[ruled,vlined,linesnumbered,titlenumbered]{algorithm2e}
\DontPrintSemicolon
\SetKwInOut{Input}{Input}

%%%%%% 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 2026}\\
\vspace{3mm}
{\Large\bf Written Assignment 1}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, May 26, 2026 at 5:00pm}\\
\end{center}

Be sure to read the assignment guideliness
(\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 \textbf{Academic
Integrity Declaration} AID01.

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

\subsection{[9 marks]}

There are many different definitions of ``little-omega'' in the literature  
(to distinguish them, we will call them $\omega_1,\dots,\omega_3$ here).  
Fix two functions $f(x),g(x)$ from $\mathbb{R}^+$ to $\mathbb{R}^+$; in particular
they are never 0.  We will say that
\begin{itemize}
\item[(i)] \emph{$f(x)\in \omega_2(g(x))$} if for all $c>0$ there exists $n_0>0$ such that
	$f(x)\geq c\cdot g(x)$ for all $x\geq n_0$,
\item[(ii)] \emph{$f(x)\in \omega_1(g(x))$} if for all $c>0$ there exists $n_0>0$ such that $f(x)> c\cdot g(x)$ for all $x\geq n_0$, 
\item[(iii)] \emph{$f(x)\in \omega_3(g(x))$} if $g(x)\in o(f(x))$.
\end{itemize}

Show that these definitions are equivalent, i.e., $f(x)\in \omega_i(g(x))$ if and
only if $f(x)\in \omega_j(g(x))$ for any $i,j$.  Your proof may use
the limit-rule (and related statements) only as far as their actual
proofs are in the course notes; otherwise you need to re-prove the
statement (but you may copy and modify proofs from the course notes).

Recall that the easiest way to prove that a number of statements are 
equivalent is to prove a circle of implications among them, 
e.g.~(i)$\Rightarrow$(ii)$\Rightarrow$(iii)$\Rightarrow$(i).
Picking the circle to prove is up to you, but state clearly what you
are proving.

\subsection{[3+3+3={9} marks]}

Consider the following (rather strange) code-fragment:

\begin{algorithm}[H]
\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{[7 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+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 $\mathrm{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 implementation 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
$\alg{decrease-key}$ with $O(f(n))$ run-time.    

\end{enumerate}
\end{document}