\documentclass[12pt]{article}

\usepackage{algo,fullpage,url,amsmath,amsthm,amssymb,epsfig,color,xspace}
\usepackage[
pdftitle={CS 240 Assignment 1},
pdfsubject={University of Waterloo, CS 240, Winter 2017},
pdfauthor={}]
{hyperref}

\usepackage{enumitem}
\usepackage{qtree}
\qtreecenterfalse

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

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 - Spring 2017}\\
\vspace{2mm}
{\Large\bf Assignment 1}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, May 17th, 5pm}
\end{center}

Please refer to the course webpage for guidelines on submission. Submit your written solutions electronically as a PDF with file name \texttt{a01wp.pdf} using MarkUs. We will also accept individual question files named \texttt{a01q1w.pdf}, \texttt{a01q2w.pdf}, etc., if you wish to submit questions as you complete them.

Unless the base is explicitly specified, we assume in all questions that the logarithm operation is base 2.

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

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

Provide a complete proof of the following statements from first principles (i.e., using the original definitions of order notation). You may use any mathematical facts presented in lecture or in the course notes without proof.

\begin{enumerate}[label=(\alph*)]
\item $42n^{8} + 16n^{6} + 5n\log(n) + 2017 \in O(n^{10})$.

\item $n^{3}(\log(n))^{2} \in \Omega(n^{3})$.

\item $n^{5} / (n^{3} + 3n) \in \Theta(n^{2})$.

\item $n^{n} \in \omega(n^{100})$.

\end{enumerate}

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

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

Prove or disprove each of the following statements. To prove or disprove a statement, you must provide a proof based on the definitions of each order notation. However, it is sufficient to provide an example with justification to prove an existence statement or to disprove a universal statement.

\begin{enumerate}[label=(\alph*)]
\item There exist functions $f(n)$ and $g(n)$ such that $f(n) \in o(g(n))$ and $f(n) \in \omega(g(n))$.

\item For all $k \geq 1$, $(\log(n))^{k} \in o(n)$.

\item $1 + n + n^{2} + \cdots + n^{k-1} \in \Theta(n^{k})$.

\end{enumerate}

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

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

Give an analysis of the running times of each of the following blocks of pseudocode using order notation. A formal proof is not required, but you should show your work and justify your answer. For full marks, your bounds must be as tight as possible.

\begin{enumerate}[label=(\alph*)]
\item 
\begin{verbatim}
for i from 1 to n*n do
    j = n
    while j > 0 do
        j = j - 1
\end{verbatim}

\item
\begin{verbatim}
x = 0
for i from 1 to n*n do
    for j from 1 to i*i do
        x = x + 1
\end{verbatim}

\item 
\begin{verbatim}
x = 1
for i from 1 to n do
    x = x * 2
    for j from 1 to x do
        y = y + 1
\end{verbatim}

\end{enumerate}

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

\subsection{[5+5=10 marks]}

\begin{enumerate}[label=(\alph*)]
\item Heapify the following array in a min-heap using the techniques presented in the course notes. List each heap operation being performed and on which element, and present the state of the heap after each operation.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
4 & 2 & 7 & 5 & 1 & 8 & 9 & 6 & 3 \\
\hline
\end{tabular}
\end{center}

\item Remove the keys 1, 2, 3, 4, and 5 from the following min-heap in that order. List each comparison and operation being performed and on which element, and present the state of the heap after each operation.
\begin{center}
\Tree[ .1 [ .2 [ .3 6 5 ] 4 ] [ .7 8 9 ] ]
\end{center}
\end{enumerate}

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

\newpage

\subsection{[2+3(+5 bonus)=5(+5) marks]}

A \textit{ternary heap} is a generalization of heaps that uses a ternary tree, or a tree where each node may have up to three children. Ternary heaps share all of the same properties as regular heaps regarding the insertion and position of nodes; namely, all levels except possibly the bottom level of a ternary heap are filled, the bottom level of a ternary heap is filled from left to right, and the value stored in a node must be larger than the values stored in any of the node's children.

\begin{enumerate}[label=(\alph*)]
\item Explain how you can store a ternary heap as an array $A$ of size $O(n)$ such that the root of the ternary heap is located at position $A[0]$. Explain how you can find the parent and all children of an arbitrary node $A[i]$ in the ternary heap.

\item Prove that the height of a ternary heap with $n$ nodes is at most $\frac{\log(2n-1)}{\log(3)}$.

\item \textit{Bonus.} Given two ternary heaps $H_{1}$ and $H_{2}$ that are both of the same height and both full, describe an algorithm to \textit{merge} $H_{1}$ and $H_{2}$; that is, to create a new ternary heap $H$ that contains all elements in both $H_{1}$ and $H_{2}$. The running time of your algorithm should be $O(\log(n))$, where $n = |H_{1}| = |H_{2}|$. You do not need to prove the correctness of your algorithm, but you must justify the running time.

You may assume that $H_{1}$, $H_{2}$, and $H$ are implemented as tree data structures rather than arrays, and that all elements in $H_{1}$ and $H_{2}$ are distinct.

\end{enumerate}

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

\end{document}
