\documentclass[boldsans]{article}
\usepackage{ccfonts,fullpage,amsmath,amssymb}
\usepackage{hyperref}
\title{CSC165, Winter 2013\\
Assignment 3\\
Due Wednesday April 3rd, 11:59 p.m.}
\renewcommand{\today}{~}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
\begin{document}
\maketitle

This assignment gives you some practice with asymptotic proofs
(big-Oh, big-Omega, big-Theta), halting problem reductions, and limits.
You may work in groups of no more than three
students, and you should produce a single solution in a PDF file named
\texttt{a3.pdf}, submitted to
\href{https://stanley.cdf.toronto.edu/markus/csc165-2013-01}{MarkUs}.
You must produce \texttt{a3.pdf} by \textbf{typing} your
solutions and processing the typed input into a PDF with your
favourite word processor or typesetting program.  Handwritten and
then scanned PDF files are huge and often illegible.

You will receive 20\% of the marks for any question you either leave
blank, or write ``I cannot answer this.''  You will receive
substantial parts marks if you present the outline of a proof/disproof
with clear indication of the steps you are unable to complete.

All your proofs must use the course proof structure.  If you are not
sure whether to prove or disprove, write the proof structure, making
it clear which steps you cannot justify.

\begin{enumerate}
\item \textbf{Prove or disprove:} $5n^3 - 3n^2 + 2n + 3$ is in
  $\mathcal{O}(2n^3 -n^2 + n + 1)$.\vfill
\item \textbf{Prove or disprove:} $5n^3 - 3n^2 + 2n + 3$ is in
  $\Omega(2n^3 -n^2 + n + 1)$. \vfill
\item \textbf{Prove or disprove:} $15\ln n$ is in $\Omega(n/3)$.
  \textbf{Hint:} Consider using limit techniques from calculus,
  including l'H\^{o}pital's rule as part
  of this proof.  Please talk to your TA/instructor/Help Centre when
  needed.\vfill
\item \textbf{Prove or disprove:} $3^n$ is in $\mathcal{O}(2^n)$.
  \textbf{Hint:} Consider using the limit techniques of calculus and
  notice that
  \begin{equation*}
    \lim_{n\rightarrow \infty} \frac{3^n}{2^n} =
    \lim_{n\rightarrow\infty} \left(\frac{3}{2}\right)^n
  \end{equation*}
\item Prove
  that the function \verb+true_that+ below is not computable:
\begin{verbatim}
def true_that(f, I, n) :
   """
   Return true when the if statement on line n of function f
   executes on input I, and false otherwise.
   """
\end{verbatim}
Emulate the technique from the course notes to reduce \verb+halt+ to
\verb+true_that+\vfill
\end{enumerate}


\end{document}
