\documentclass[12pt]{article} 
\newif\ifenriched
\enrichedtrue

\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} % for version control
\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)]}
\renewcommand{\thesubsection}{Question \arabic{subsection}}


\begin{document}

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

Be sure to read the assignment guideliness
(\url{http://www.student.cs.uwaterloo.ca/~cs240e/w23/guidelines.pdf}).
Submit your solutions electronically
to MarkUs as \textbf{individual} PDF files named
a1q1.pdf, a1q2.pdf, \dots (one per question).

Ensure you have read, signed, and submitted the \textbf{Academic
Integrity Declaration} AID01.TXT.

\textbf{Grace period:} submissions made before 11:59PM on Jan. 19,
will be accepted without penalty.
Please note that submissions made after 11:59PM
\textbf{will not be graded} and may only be reviewed for feedback.

\addtocounter{subsection}{0}

\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(+3)={\color{red}6(+3)} 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)] (Bonus)	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+3+7+2(+1)=14(+1)]}

We define the Fibonacci sequence $\{ t_n \}$ by
$$
t_n = \begin{cases}
0 &\text{if } n = 0, \\
1 &\text{if } n = 1, \\
t_{n-1} + t_{n-2}, &\text{if } {n \geq 2}
\end{cases}
$$

\begin{itemize}
\item[(a)] Show that $t_n \geq \left( {\sqrt{2}} \right)^n$ for $n\geq 8$.
\item[(b)] Find a constant $k < 1$ such that $t_n \leq 2^{kn}$ for $n \geq 0$. Justify
that the inequality holds for your choice of $k$.
\item[(c)] 
One way to compute $t_n$
uses matrix exponentiation. We can express the linear
system
$$
\begin{cases}
t_1 = t_1 \\
t_2 = t_0 + t_1
\end{cases}
$$
in matrix notation:
\begin{align*}
\begin{bmatrix}
t_1 \\ t_2
\end{bmatrix}
&= \begin{bmatrix}
0 & 1 \\ 1 & 1
\end{bmatrix}
\begin{bmatrix}
t_0 \\ t_1
\end{bmatrix}.
\end{align*}
In general,
$$
\begin{bmatrix}
t_n \\ t_{n+1}
\end{bmatrix}
= 
\begin{bmatrix}
0 & 1 \\ 1 & 1
\end{bmatrix}^n \cdot \begin{bmatrix}
t_0 \\ t_1
\end{bmatrix}.
$$

Give an algorithm $\mathcal{A}$ to compute {\color{red} $t_n$}
that uses
$O(\log n)$ \textbf{$2 \times 2$ matrix multiplications}.

\item[(d)] Argue that 4 additions and 8
multiplications (of integers) suffice to compute 
the product of two $2 \times 2$
matrices with integer entries
(hence the runtime of your algorithm
$\mathcal{A}$
in (c) is $O(\log n)$).

\item[(e)] (Bonus) Another algorithm
to compute $t_n$ is\pagebreak

\begin{algorithm}
\caption{{ $\mathcal{B}$ (int $n$)}}
\Input{$n\geq 0$}
	\lIf{$n == 0$}{return 0}
	\lIf{$n == 1$}{return 1}
	create array of integers $T[0 .. n]$\;
	{\color{red} $T[0] \gets 0; T[1] \gets 1$ \;}
	\For{$i \gets 2$ to $n$}{
		$T[i] \gets T[i-1] + T[i-2]$
	}
	return $T[n]$
\end{algorithm}

Explain why the $O(\log n)$
algorithm $\mathcal{A}$ is likely to
be slower
than the $\Omega(n)$ algorithm
$\mathcal{B}$ when
implemented on an actual machine.
\end{itemize}

\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. 

\end{document}
