\documentclass[12pt]{article}
\usepackage[pdftitle={tut1},pdfsubject={Tutorial 1},pdfauthor={Wei Sun}]{hyperref}

%amsmath is a packaged use for typesetting math
%amsfonts is required for special fonts, e.g. blackboard bold (for denoting real numbers, etc.)
\usepackage{amsmath,amsfonts}

%tikz is the package used for trees
\usepackage{tikz}

\begin{document}
\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240R Spring 2017}\\
\vspace{2mm}
{\Large\bf Tutorial 1}\\
\vspace{3mm}
\textbf{Monday, May 15}
\end{center}

\section*{Problem 1 - Order Notation}

a) Prove $\frac{1} {n} \in o(1)$\\\\
b) Prove $2^{\log^2 n} \in \omega(n)$\\\\
c) Prove $log(n!) \in \Omega(n*log(n))$

\section*{Problem 2 - Separate Bounds}

Prove this algorithm is in $\Theta(n^2)$ by proving separate upper and lower bounds.

\begin{verbatim}
sum := 0
for i=1 to n
  for j=1 to i
    sum = sum + (i - j)^2
    sum = sum/i
return sum
\end{verbatim}

\section*{Problem 3 - More Algorithms Analysis}

Analyze the runtime of the algorithm below and prove a $\Theta$ bound. 

\begin{verbatim}
for i=1 to n
  j := i
  while j < n do
    j = 2*j
\end{verbatim}

Hint: Stirling's formula states that $n! \approx \sqrt{2 \pi n}(\frac {n} {e})^n$

\section*{Problem 4 - Heap Insert and Delete}

Insert 17, then 8 on the heap below. Then perform delete-max on the original heap.

\begin{center}\begin{tikzpicture}[
  level distance=45 pt,
  every node/.style={circle,draw},
  level 1/.style={sibling distance=200 pt},
  level 2/.style={sibling distance=100 pt},
  level 3/.style={sibling distance=60 pt}
]
  \node {7}
    child {node {6}
      child {node {5}}
      child {node {4}}
    }
    child {node {3}
      child {node {2}}
      child {node {1}}
    };
\end{tikzpicture}\end{center}


\end{document}