\documentclass[12pt]{article}

\usepackage{tikz,fullpage,url,amssymb,epsfig,color,xspace}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 240 Assignment 1},%
pdfsubject={University of Waterloo, CS 240, Fall 2020},%
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 Fall 2020}\\
\vspace{2mm}
{\Large\bf Assignment 1}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, Sept 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

The integrity of the grade you receive in this course is very important to you and 
the University of Waterloo.  As part of every asessment in this course you must read 
and sign an Academic Integrity Declaration before you start working on the assessment and
submit it \textbf{before the deadline of Sept 23} along with your answers to the 
assignment; i.e. \textbf{read, sign and submit A01-AID.txt now or as soon as possible}.
The agreement will indicate what you must do to ensure the integrity of your grade.
If you are having difficulties with the assignment, course staff are there to help
(provided it isn't last minute). \\
~\\
\textbf{The Academic Integrity Declaration must be signed and submitted on time or the
assessment will not be marked.} \\
~\\
Please read
\url{http://www.student.cs.uwaterloo.ca/~cs240/f20/guidelines/guidelines.pdf} 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, ... , a1q5.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{Remember, late assignments will not be marked (\#3).} \\
~\\
Note: you may assume all logarithms are base 2 logarithms:  $\log = \log_2$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[4+4+4+4+4=20 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} $12n^4 - 11n^2 + 10 \in \Theta(n^4)$
\part{b} $n^2(\log n)^{1.0001} \in \Omega(n^2)$
\part{c} $\frac{n^2}{n+\log n} \in \Theta(n)$
\part{d} $n^{n} \in \omega(n^{20})$
\part{e} $1000n \in o(n \log n)$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[4+4+4+4=16 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^4(7 + 3\cos 2n)$ versus $g(n)= 7n^4 + 5n^3 + 3n$
\part{b} $f(n)=10^n+99n^{10}$ versus $g(n)=75^n+25n^{27}$
\part{c} $f(n)=\sqrt{n}$ versus $g(n)=(\log{n})^{3}$
\part{d} $f(n) = \log \log n$ versus $g(n) = (\log \log \log n)^8$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[4+4+4=12 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{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+4=16 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}
  x = 0
  for i = 1 to n + 12 do
     x = x * 4
     for j = 389 to 20100 do 
        x = x * 20
\end{verbatim}
\part{b}
\begin{verbatim}
   x = 1
   y = 0
   for i = 1 to n do
      x = x * 5
      for j = 1 to x do 
         y = y + 1
\end{verbatim}

\part{c}
\begin{verbatim}
x := -42
y := 1
while y < 5n do
   z := n * n * n
   while z > y do
      x := 2 - x
      z := z - y
   y := y + 5
\end{verbatim}

\part{d}
\begin{verbatim}
x = 0
for i = 1 to sqr(n)     // i.e. n^2
   for j = 1 to ceiling( log(i) )
      x = x + 1
\end{verbatim}

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[4+4=8 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 the property that the key of a parent is larger than or equal to
all the keys of their children. \\
~\\
You may assume that $d$ is a constant. \\

\begin{itemize}
\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; i.e. a $\Theta$-bound. 

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
