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

%%%%%%%% version control
% \newcommand{\showSolution}{show them} % comment out this line if not wanted
	% i.e., if you'd like to see suggested solutions
%\newcommand{\showMarking}{show them} % comment out this line if not wanted
	% i.e., if you'd like to see suggested marking scheme
%\newcommand{\suppressSpace}{show them} % this should usually be commented out
	% but enable it if building exams that have lots of whitespace 

%%%%%%% a few packages.  Most of them are not actually needed for the questons 
% here, but some other questons from the data base might use them
\usepackage{fullpage}
\usepackage{float}
\usepackage{amsmath, amsfonts}
\usepackage{color,enumerate}
\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}


%%%% a few things that are needed for the data base, but mostly ignored here
\newenvironment{solution}
	{\ifthenelse{\isundefined{\showSolution}}
		{\expandafter\comment}{\color{blue}\hfill\break{\bf Solution Ideas}:}}
        {\ifthenelse{\isundefined{\showSolution}}%
		{\expandafter\endcomment}{}}
\newenvironment{authorship}{\expandafter\comment}{\expandafter\endcomment}
\newenvironment{usage}{\expandafter\comment}{\expandafter\endcomment}
\newenvironment{suggestedMarkingScheme}
	{\ifthenelse{\isundefined{\showMarking}}
		{\expandafter\comment}{\color{brown}\hfill\break{\bf Marking Ideas}:}}
        {\ifthenelse{\isundefined{\showMarking}}%
		{\expandafter\endcomment}{}}
\newenvironment{spaceForAnswer}
	{\ifthenelse{\isundefined{\suppressSpace}}{\expandafter\comment}{}}
        {\ifthenelse{\isundefined{\suppressSpace}}{\expandafter\endcomment}{}}

%%%%%% 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 2026}\\
\vspace{3mm}
{\Large\bf Written Assignment 1}\\
\vspace{3mm}
% \textbf{Marking Due Date: Monday, January 30, 2023 at 5pm} \\
\end{center}

Be sure to read the assignment guideliness
(\url{http://www.student.cs.uwaterloo.ca/~cs240e/w26/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{Due:} Tuesday Jan 20, 5:00PM
\textbf{Grace period:} submissions made before 8:00PM on Jan. 20,
will be accepted without penalty.
Please note that submissions made after 8:00PM
\textbf{will not be graded} and may only be reviewed for feedback.


\addtocounter{subsection}{0}

\subsection{[6 marks]}

There are many different definitions of ``little-omega'' in the literature  
(to distinguish them, we will call them $\omega_1, \omega_2,\omega_3$ here).  
Fix two functions $f(x),g(x)$ from $\mathbb{R}^+$ to $\mathbb{R}^+$; in particular
they are never 0.  We say that
\begin{itemize}
\item[(i)] \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[(ii)] \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[(iii)] \emph{$f(x)\in \omega_3(g(x))$} if the function $\tfrac{f(x)}{g(x)}$ tends to infinity.
\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+6= 9 marks]}

\begin{itemize}
\item[(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)$.''



\item[(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{[2+3+7+2(+1)=14(+1)]}

We define the Fibonacci sequence $\{ t_n \}$ by $t_0 = 1$, $t_1 = 1$, and for $n \geq 2$,
$$
t_n =
t_{n-1} + t_{n-2}.
$$

\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*}
Note that in general,
$$
\begin{bmatrix}
t_n \\ t_{n+1}
\end{bmatrix}
= 
\begin{bmatrix}
0 & 1 \\ 1 & 1
\end{bmatrix}^n \begin{bmatrix}
t_0 \\ t_1
\end{bmatrix}.
$$

Give an algorithm $\mathcal{A}$ to compute {$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

Note: as a consequence, 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]$\;
	$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{[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}


\end{document}
