\documentclass[12pt]{article}

\input{algo.sty}
\usepackage{fullpage,url,amssymb,epsfig,color,xspace}
\usepackage[
pdftitle={CS 240 Assignment 1},
pdfsubject={University of Waterloo, CS 240, Fall 2026},
pdfauthor={Arne Storjohan}]
{hyperref}

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

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 - Fall 2026}\\
\vspace{2mm}
{\Large\bf Assignment 1}\\
\vspace{3mm}
\textbf{Due Date: Tuesday September 22 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 follow the guidelines for submission on the course webpage.\\

\url{https://student.cs.uwaterloo.ca/~cs240/f26/assignments.phtml#guidelines}\\

\noindent
All logs are base 2.  There are 63 marks available; the assignment
will be marked out of 60.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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{minipage}[t]{8cm}
\begin{itemize}
\part{a} $12 n^3 +11n^2+10 \in O(n^3)$
\part{b} $12 n^3 +11n^2+10 \in \Omega(n^3)$
\part{c} $12 n^3 +11n^2+10 \in \Theta(n^3)$
\end{itemize}
\end{minipage}
\begin{minipage}[t]{8cm}
\begin{itemize}
\part{d} $1000n \in o(n \log n)$
\part{e} $n^{n} \in \omega(n^{20})$
\end{itemize}
\end{minipage}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[4+4=8 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))$.  Provide a brief justification of your answers.  In your
justification you may use any relationship or technique that is described
in class.
\begin{itemize}
\part{a} $f(n)=\sqrt{n}$ versus $g(n)=(\log{n})^{2}$
\part{b} $f(n)=n^3(5+2\cos{2n})$ versus $g(n)=4n^3 + 3n^2+5n$
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[6+6=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{b} $\min(f(n),g(n)) \in \Theta\left (\frac{f(n)g(n)}{f(n)+g(n)}\right)$  
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\subsection{[6 marks]}
Suppose $n$ is a power of two and $\theta$
is a parameter in the range $2 \leq \theta \leq 3$.  
Derive an exact closed form for the sum
$$f(n) := \sum_{i=0}^{\log_2 n} 4^i \left ( \frac{n}{2^i} \right )^{\theta}$$
in terms of $n$ and $\theta$. 
{\em Hints:} Re-write the formula as
a geometric series. Treat $\theta=2$ as a special case.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\subsection{[2+2+4+4=12 marks]}
Consider the following procedure.

\begin{verbatim}
pre: n is a positive integer
pre: v[1..n] is a binary vector of length n, 
     i.e., each entry is either 0 or 1
foo(v,n)
1.   i := 1;
2.   while i<=n and v[i]=0 do 
3        i := i+1
4    od;
5.   for j from 1 to i do
6.       print("Hello world!")
7.   od;
\end{verbatim}

\begin{itemize}
\part{a} How many possible input vectors are there are of size $n$?
\part{b} What is the worst case number of calls to print?  Give an
exact formula in terms of $n$ and justify your answer by giving an
example of a worst case input of size $n$.  {\it Note:} This is
standard pseudo-code, so the for-loop is inclusive of $i$. E.g., if
$i=1$ then the loop executes once.
\part{c} For $i \in \{1,2,\ldots,n\}$, let $S_i$ denote the subset
of inputs of size $n$ for which the number of calls to print is
$i$.  Describe what an element of $S_i$ looks like, and derive an
expression for $|S_i|$, the number of elements of $S_i$.
\part{d} What is the average case number of calls to print?  Derive
an exact closed form formula in terms of $n$.
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[5 marks]}
Prove that the following code fragment will always terminate.
\begin{verbatim}
s := 3*n  // n is an integer
while (s>0)
   if (s is even)
      s := floor(s/4)
   else
      s := 2*s
\end{verbatim}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[5 marks]}
Analyze the following piece of pseudo-code and give a
$\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.
  \begin{algorithme}
        \lign $mystery \leftarrow 0$\\ 
        \lign \pc{for} $i \leftarrow 1$ \pc{to} $3n$ \pc{do}\\
	\lign \>$mystery \leftarrow mystery\times 4$\\
        \lign \> \pc{for} $j \leftarrow 1388$ \pc{to} $2010$ \pc{do}\\
        \lign \>\> \pc{for} $k \leftarrow 4i$ \pc{to} $6i$ \pc{do}\\
        \lign \> \>\> $mystery \leftarrow mystery+k$
  \end{algorithme}
\end{document}