\documentclass[boldsans]{article}
\usepackage{ccfonts,fullpage,graphics,rotating,amsmath,amssymb}
\usepackage{hyperref}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
\title{CSC236 Fall 2016\\Assignment \#2\\ 
  {\bf due November 4th, 10 p.m.}}
\renewcommand{\today}{~}
\newcommand{\ul}{$\underline{~}$}
\newboolean{solutions}
\setboolean{solutions}{false}
\begin{document}
\maketitle\vspace{-2\baselineskip}
\noindent
These problems are to give you some practice proving facts about recurrences, and the time complexity of algorithms that are expressed as recurrences.

Your assignment must be typed to produce a PDF document
\textbf{a2.pdf} (hand-written submissions are not acceptable). You
may work on the assignment in groups of \textbf{1 or 2} and submit a single assignment for the entire group on
\href{https://markus.cdf.toronto.edu/csc236-2016-09}{MarkUs}. Your teammates must be \textbf{different} than all teammamtes you had in Assignment 1.
\begin{enumerate}
\item Consider the Fibonacci function $f$:
  \begin{equation*}
    f(n) =
    \begin{cases}
      0, & \text{if $n = 0$} \\
      1, & \text{if $n = 1$} \\
      f(n-2) + f(n-1) & \text{if }n> 1
    \end{cases}
  \end{equation*}
  
  Prove $f(n-1)*f(m-1)+f(n+1)*f(m+1)+f(n)f(m) > f(n+m)$ for $n,m\geq 1$.
\ifthenelse{\boolean{solutions}}{\input{fibonacci_solutions.tex}}{}
  
  
\item \begin{enumerate}
\item Find a recurrence relation, $T(n)$, for number of distinct full binary trees with $n$ nodes. Show how you find the relation.

\item Without using a closed form, prove $T(n) \geq 2^{(n-1)/2}$ for most odd numbers.
\end{enumerate} 
   
\ifthenelse{\boolean{solutions}}{\input{fbt_solutions.tex}}{}

\item \begin{enumerate}
\item Find a recurrence relation, $T(n)$, for number of microorganisms in a microbial culture in which every 2 hours the number of microorganisms is quadrupled and also three times as many of the microorganisms die 4 hours after creation.  There are initially 4 microorganisms in the culture. 

\item Without using a closed form, prove $T(n)$ is strictly increasing. 

\item Compute the closed form of $T(n)$ using unwinding (repeated substitution).

\item Prove the closed form, computed in part (c), is correct.  
\end{enumerate} 

\ifthenelse{\boolean{solutions}}{\input{microorganism_solutions.tex}}{}

\item \begin{enumerate}
\item Find a recurrence relation, $T(n)$, for number of distinct ways that a postage of $n$ cents can be made by 4-cent, 6-cent, and 10-cent stamps for most even numbers. 

\item Without using a closed form, prove $T(n)$ is non-decreasing. 
\end{enumerate}
\ifthenelse{\boolean{solutions}}{\input{postage_solutions.tex}}{}
 
\item \begin{enumerate}

\item Devise a brute-force algorithm in Python\footnote{or any other common programming language} notation, \textbf {max-sum}, to find the largest sum of consecutive terms of a sequence of $n$ positive and negative numbers.

\item Find the worst-case time complexity of \textbf {max-sum}.

\item Devise a divide-and-conquer algorithm to find \textbf {max-sum}, by splitting the sequence to halves, and finding \textbf {max-sum} in each. Note that the maximum sum of consecutive terms can include terms in both halves.

\item Find a recurrence relation for the worst-case time complexity of the divide-and-conquer \textbf {max-sum}.

\item How does the time complexity of the the divide-and-conquer algorithm compare with that of the brute-force one?
\end{enumerate}

\ifthenelse{\boolean{solutions}}{\input{max_sum_solutions.tex}}{}
  
\end{enumerate}
\end{document}
