\documentclass{article}
\usepackage{fullpage}
\usepackage{amsmath,amssymb,proof, multirow,multicol}
\usepackage{hyperref}
\title{CSC165, Winter 2015\\
Assignment 3\\
Due  Apr 07, 11:59 p.m.}
\renewcommand{\today}{~}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
  
  
\newcommand*{\floor}[2][]{#1\lfloor{#2}#1\rfloor}
\newcommand*{\ceil}[2][]{#1\lceil{#2}#1\rceil}

  
\begin{document}
\maketitle

%\noindent The aim of this assignment is for you to practice using quantifiers,
%implications, logical connectives and expressions.  

\begin{itemize}
	\item You may work in groups of no more than \textbf{two} students, and you should 
	produce a single solution in a PDF file named \texttt{a3.pdf}, submitted to
	\href{https://markus.cdf.toronto.edu/csc165-2015-01}{MarkUs}. Submissions must be \textbf{typed}. 
	\item The size of the PDF file \textbf{must} be less than \textbf{1MB}.
	\item \textbf{Late submission policy}: Each \textbf{group} can benefit from 
	\textbf{one} time 24-hour	grace period with no penalty.
	
	If you use your grace period for one assignment, then change your group for the 
	next one, and your new group-mate has not use his/her grace period, the new 
	group \textbf{can} submit late by 24 hours. 
	However, if both students in the group have used their grace period, the new group 
	\textbf{cannot} submit late. 
\end{itemize}
\vspace{2\baselineskip}

\noindent IMPORTANT: You \textbf{must} use the proof structures and format of this course. 
Otherwise, you won't get full mark even if your answers are correct. 

\begin{enumerate}
\setlength\itemsep{2em}
\item \textbf{Prove} or \textbf{disprove} each of the following claims.

You may assume that $f:\mathbb N\to \mathbb R^{\geq 0}$ and $g:\mathbb N\to \mathbb R^{\geq 0}$.


\begin{enumerate}
\setlength\itemsep{1em}
	\item Let $f(n)=n\lfloor \frac{n}{2}\rfloor$, and $g(n)=n^2-2n+1$. 
	
	Then $f\in\Theta(g).$
	\item Let $f(n)=n^4+3n^3+n^2-1$, and $g(n)=n^5-8n^3-n$. 
	
	Then $f\in\Theta(g).$
	
	\item Let $f(n)=n^{n}$, and $g(n)=n^{n-5}$. 
	
	Then $f\in\Theta(g).$
\end{enumerate}

\newpage
\item Prove a \textbf{tight bound} on the worst-case running time of each of the following algorithms
\begin{enumerate}
	\setlength\itemsep{2em}
	\item 
	\begin{verbatim}
	def mystery1(L):
	""" L is a non-empty list of length len(L) = n. """
	    if L[0] is even:
	       i=0
	       while i <n^2:
	          L[0] = L[0] + L[i/n]
	          i=i+1
	    else:
	       i=0
	       while i < n-1:
	          L[0] = L[0] - L[i]
	          i=i+1
	\end{verbatim}
	
	\item 
	\begin{verbatim}
	def mystery2(L):
	""" L is a non-empty list of length len(L) = n. """
	    step = 1
	    index = 0
	    while index < len(L):
	       index = index + step
	       step = step + 1
	\end{verbatim}
	
\end{enumerate}

\item Prove each of the following statements by induction (in all parts, assume that $n\in\mathbb N$) 
\begin{enumerate}
	\setlength\itemsep{2em}
	\item $1 + 6 + 11 + 16+...+(5n - 4) = \frac{n(5n-3)}{2}$, $n\ge 1$.
	\item For all natural numbers $n\ge 3$,
	
	$4^3 + 4^4 + 4^5 +...+4^n = \frac{4(4^n - 16)}{3}$
	
	\item $\sqrt{n}<\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+...+ \frac{1}{\sqrt{n}}$, $n\ge 2$.
\end{enumerate}

\end{enumerate}

\end{document}
