\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{tikz,fullpage,url,amssymb,epsfig,color,xspace}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 240 Assignment 1},%
pdfsubject={University of Waterloo, CS 240, Spring 2024},%
pdfauthor={MP}]{hyperref}
%\RequirePackage{pstricks,pst-node,pst-tree} % draw trees, requires using xetex
\newlength{\nodeLength}
\newcommand{\Node}{A}
\newcommand{\setnode}[1]{
  \settowidth{\nodeLength}{#1}
  \renewcommand{\Node}[1]{
    \Tcircle[name=#1]{\makebox[\nodeLength]{##1}}
  }
}
\setnode{99}


\renewcommand{\thesubsection}{Problem \arabic{subsection}}

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 Spring 2024}\\
\vspace{2mm}
{\Large\bf Assignment 1}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, May 21 at 5:00pm}
\end{center}

\definecolor{care}{rgb}{0,0,0}
\def\question#1{\item[\bf #1.]}
\def\part#1{\item[\bf #1)]}
\newcommand{\pc}[1]{\mbox{\textbf{#1}}} % pseudocode

\noindent Please read the following link for guidelines on submission:
\vspace{-2mm}
\begin{center}
\url{https://student.cs.uwaterloo.ca/~cs240/w24/assignments.phtml#guidelines}
\end{center}

\vspace{-1mm}
\noindent \textbf{Each question must be submitted individually to
MarkUs as a PDF} with the corresponding file names: 
\texttt{a1q1.pdf}, \texttt{a1q2.pdf}, $\ldots$. 
It is a good idea to submit questions as you go so you aren’t trying to create several PDF files at the last minute.

\vspace{2mm}
\noindent \textbf{Late Policy}: Assignments are due at \textbf{5:00pm}, with the grace period until 11:59pm.

\vspace{3mm}
\noindent \textbf{Notes:}
\begin{itemize}
    \item Logarithms are in base 2, if not mentioned otherwise.
    \item A positive function is a function that takes positive real values.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[3+3+3+3=12 marks]}

Provide a complete proof of the following statements from first principles
(i.e., using the original definitions of order notation).
\begin{itemize}
\part{a} $27n^7 +17n^3\log n + 2024$ is $O(n^9)$
\part{b} $n^2(\log n)^{1.0001}$ is $\Omega(n^2)$
\part{c} $\frac{n^2}{n+\log n}$ is $\Theta(n)$
\part{d} $n^{n}$ is $\omega(n^{20})$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[3+3+3=9 marks]}
For each pair of the following functions, fill in the correct asymptotic
notation among $\Theta$, $o$, and $\omega$ in the statement $f(n)\in
\sqcup(g(n))$.  Prove the relationship using any relationship or technique that described
in class.
\begin{itemize}
\part{a} $f(n)= n^2+27n\log{n}+2024$ versus $g(n)= n^2\log{n}+2024$
\part{b} $f(n)=10^n+99n^{10}$ versus $g(n)=75^n+25n^{27}$
\part{c} $f(n) = \log \log n$ versus $g(n) = (\log \log \log n)^8$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[4+4+4+4=16 marks]}
Prove or disprove each of the following statements.  To prove a
statement, you should provide a formal proof that is based on the
definitions of the order notations.  To disprove a statement, you can
either provide a counter example and explain it or provide a formal proof.
All functions are positive functions.
\begin{itemize}
\part{a} $f(n) \not \in o(g(n))$ and $f(n) \not \in \omega(g(n)) \Rightarrow f(n) \in \Theta(g(n))$
\part{b} $f(n)\in \Theta(g(n))$ and $h(n)\in \Theta(g(n)) \Rightarrow \frac{f(n)}{h(n)}\in \Theta(1)$ 
\part{c} $f(n)\in \Theta(g(n))\Rightarrow 2^{f(n)} \in \Theta(2^{g(n)})$
\part{d} $\min(f(n),g(n)) \in \Theta\left (\frac{f(n)g(n)}{f(n)+g(n)}\right)$  
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{[4+4+4=12 marks]}

Analyze the following piece of pseudocode and give a tight ($\Theta$) bound on the running time as a function of $n$.
Show your work. 
A formal proof is not required, but you should justify your answer (in all cases, $n$ is assumed to be a positive integer).

\begin{itemize}
\part{a}
\begin{verbatim}
  s = 0
  for i = 1 to n do
     for j = i to n do
        if i == j then
           k = n
           while k > 0 do
              s = s + 1
              k = k/3
\end{verbatim}

\part{b}
\begin{verbatim}
  s = 2024
  for i = 1 to n*n do
     for j = 1 to i*i do
        s = s + 13
\end{verbatim}

\part{c}
\begin{verbatim}
  s = 13
  i = 1
  while i < 10n do
     j = n^5  // n to the power 5
     while j > i do
        s = s + 7
        j = j - i
     i = i + 10
\end{verbatim}
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[2+4=6 marks]}
Dr. I.~M.~Smart has invented a new class of functions, denoted $O'(f)$: A function $f(n)$ is in $O'(g)$ if there is a constant $c>0$ such that $f(n)\le cg(n)$ for all $n \ge 0$.    
Assume that all functions are defined on non-negative integers and take positive real values (i.e. the domain is non-negative integers and the range is positive reals).

\begin{itemize}
\part{a} Prove that $f(n)\in O'(g(n))$ implies that $f(n)\in O(g(n))$.
\part{b} Prove that $f(n)\in O(g(n))$ implies that $f(n)\in O'(g(n))$.
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{document}
