\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools,algorithm,algorithmicx,algpseudocode}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 240 Assignment 1},%
pdfsubject={University of Waterloo, CS 240, Winter 2023},%
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}

\newcommand{\alg}[1]{\ensuremath\mbox{\it #1}}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\renewcommand{\thesubsection}{Question \arabic{subsection}}

\newcounter{algorithmeligne}
\newcommand{\instr}[1]{%\underline
                        {\bf #1}}
\newcommand{\nomproc}[1]{{\rm\bf #1}}
\newenvironment{algorithme}
        {
        \setcounter{algorithmeligne}{0}

        \newcommand{\lign}{
                \stepcounter{algorithmeligne}
                {\footnotesize \arabic{algorithmeligne}.}\>
                }
        \begin{center}
        \begin{tabular}{|c|}
        \hline
        \begin{minipage}{1cm}
        \small
        \,
        \ \ \\[-11mm]
        \begin{tabbing}
\hskip1cm\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\\\kill
        }
        {
        \end{tabbing}
        \ \ \\[-8mm]
        \end{minipage}
        \\\hline
        \end{tabular}
        \end{center}
        }


\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 Winter 2024}\\
\vspace{2mm}
{\Large\bf Assignment 1}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, January 23 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
Please read
\url{https://student.cs.uwaterloo.ca/~cs240/w24/assignments.phtml#guidelines} for guidelines on submission.  
\textbf{Each question must be submitted individually to MarkUs as a PDF} with the corresponding file names: 
a1q1.pdf, a1q2.pdf, ... , a1q6.pdf . 
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. \\
~\\
\textbf{Late Policy:} Assignments are due at {\bf 5:00pm}, with the grace period until 11:59pm. \\  
~\\

{\bf{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+3=15 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} $10n^5 \log{n} + 42n^4  - 15n^2 \in O(n^5 \log{n} )$
\part{b} $2n^4 - 10 n^2  + 5n\in \Omega(n^4)$
\part{c} 1 + ($n^2 \mod{10})\in \Theta(1)$
\part{d} $3^n \in o(3.1^n)$
\part{e} $ n^2\in \omega(n^{1.9})$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[2+4=6 marks]}

Prove  the following statements based on the definitions of the order notations.
All functions take positive values.

\begin{itemize}

\part{a} If $f(n) \in \omega(1)$, then $f(n) h(n) \in \omega(h(n)).$
\part{b} If
$f(n) \in \Theta(g(n)), h(n) \in \Theta(r(n))$, and $g(n) \in o(r(n))$ then $f(n) \in o(h(n)).$
\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 described in class. 

\begin{itemize}
\part{a} $f(n) =  5 n + 7n^2 \log{n}$ versus $g(n) = n^2 \sqrt{n} $
\part{b} $f(n) =n!$ versus $g(n) = n^{100}$
\part{c} $f(n) = 2^n$ versus $g(n) = 2^{\cos{n}} $
\end{itemize}



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


Analyze the following pieces 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{enumerate}

\part{a}

\begin{verbatim}
s := 0  
for i=1 to n * n * n do
   for j=1 to i * i * i * i do
      s := s + 1
\end{verbatim}


\part{b}
\begin{verbatim}
p = 1    
s = 0  
for i = 1 to n do
   p = p * 2
   for j = 1 to p do
      s = s + 1
\end{verbatim}

\part{c}
\begin{verbatim}
s = 0
i = 1
while i <= n do
    j = n * n * n * n
    while j > 0 do
        s = s + 1 
        j = j - i
    i = i * 2
\end{verbatim}

\part{d}
For this question, you can derive $O$ bound, but it must be as tight as possible.
\begin{verbatim}
foo(A[0...n-1]) # assume n>=1 is a power of two
   if n <= 1
       return
   print("x")
   foo(A[0...n/4-1]
   foo(A[n/4...n/2-1]
\end{verbatim}


\end{enumerate}


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

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

True or false? For each of the following assertions, indicate whether it is 
true or false. If true, prove it; if false, give a counter-example
and briefly justify it. 
\begin{enumerate}
\part{a}  $f(n)$ is  $\Theta(f(n/2))$, where $f$ takes positive values.
\part{b}  $1 + n + n^{2} + \cdots + n^{k-1} \in \Theta(n^{k})$.
\end{enumerate}





\subsection{[1+4=5 marks]}

For this problem, assume that we only deal with functions that 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).
Dr. I.~M.~Smart has recently  invented a new class of functions, denoted $O'(f)$. A function $g(n)$ is in $O'(f)$ if there is a constant $c>0$ such that $g(n)\le cf(n)$ for all $n\ge 0$.    
Prove  the following statements about relationship between $O(f)$ and $O'(f)$. 

\begin{itemize}
\part{a} If $g(n)\in O'(f(n))$, then $g(n)\in O(f(n))$
\part{b} If $g(n)\in O(f(n))$, then $g(n)\in O'(f(n))$ 
\end{itemize}



\end{document}