
\documentclass[10pt]{article}
\usepackage{amsmath,amssymb,amsfonts,fancyhdr}
\usepackage{graphicx}
%
\setlength{\textheight}{9in}
\setlength{\topmargin}{-0.75in}
\setlength{\textwidth}{7in}
\setlength{\oddsidemargin}{-.2in}
\setlength{\parskip}{6pt}
\setlength{\parindent}{0pt}
%\usepackage{fullpage}
\renewcommand{\headrulewidth}{1pt}
\setlength{\headsep}{1cm}
% \usepackage{txfonts}
\usepackage{newcent}
\usepackage{fancyhdr}
\usepackage{multirow}   % for table formatting
\usepackage{hyperref}  % for weblinks in pdf
\usepackage{color}


\newcommand{\ds}{\displaystyle} 
\newcommand{\QQ}{{\mathbb{Q}}} % blackboard Q
\newcommand{\Qbar}{{\overline{\QQ}}} % blackboard Qbar
\newcommand{\ZZ}{{\mathbb{Z}}} % blackboard Z
\newcommand{\NN}{{\mathbb{N}}} % blackboard N
\newcommand{\CC}{{\mathbb{C}}} % blackboard C
\newcommand{\Zplus}{{\mathbb{Z^+}}} % blackboard Z^+
\newcommand{\FF}{{\mathbb{F}}} % blackboard F
\newcommand{\RR}{{\mathbb R}} % blackboard R
\newcommand{\Rtwo}{{\mathbb R^2}} % blackboard R^2
\newcommand{\Rthree}{{\mathbb R^3}} % blackboard R^3
\newcommand{\RRn}{{\mathbb R^n}} % blackboard R^n
\newcommand{\D}{{\cdot}} % dot
\def\mod#1{{\ifmmode\text{\rm\ (mod~$#1$)}
\else\discretionary{}{}{\hbox{ }}\rm(mod~$#1$)\fi}}

\def\tra{70}   %text rotation angle in table header
\newcommand{\tablehead}[1]{\rotatebox{\tra}{\scriptsize{#1}}}


%----------- colours ------------------------------------------------------
\definecolor{SFUred}{rgb}{0.60547,0.140625,0.17969}
\definecolor{SFUblue}{rgb}{.1602, .2734, .51172}
\definecolor{SFUgrey}{rgb}{.28515,.28125,.25}

\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083}
\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179}
\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894}
\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894}
\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000}
\definecolor{Black}{rgb}{0.0,0.0,0.0}
\definecolor{FuncColor}{rgb}{1.0,0.0,0.0}
%------------------------------------------------------------------------------
%amps stuff

\usepackage{enumitem}
\setlist[enumerate,1]{label=}
\setlist[enumerate,2]{label=\Alph*.}
\setlist[enumerate,3]{label=\arabic*.}
\setlist[enumerate,4]{label=(\alph*)}



% check boxes for after instructors questions
\newcommand{\insertcheckboxes}{
\begin{center}
\fbox{
\begin{tabular}{ccccc}
done & checked & corrected & study MT & study final \\
$\Box$ &  $\Box$ &  $\Box$ &  $\Box$ &  $\Box$
\end{tabular}
}
\end{center}
}


% standard basis vectors
\def\ihat{{\bf \hat{i}}}
\def\jhat{{\bf \hat{j}}}
\def\khat{{\bf \hat{k}}}

% vector arrow notation
\newcommand{\bvec}[1]{\vec{ \bf #1}}  % absolute value


\newcommand{\twovec}[2]{\left[\begin{array}{c}
#1\\ #2\\ \end{array}\right] }

\newcommand{\closethegap}{\vspace{-2mm} }

\newcommand{\threevec}[3]{\left[\begin{array}{c}
#1\\ #2\\ #3\\ \end{array}\right] }

\newenvironment{soln}[1]{ \textit{Solution #1:} }{\medskip}

\pagestyle{plain}

%------------------------------------------------
% different types of labels for lists
% 1) type of label
%\renewcommand{\theenumi}{\arabic{enumi}}   default
%\renewcommand{\theenumi}{\alph{enumi}}     alphabetic   (use capital A for capitals)
%\renewcommand{\theenumi}{\roman{enumi}}    roman numerals (use capital R for capitals)
%
% 2) formatting of label
%\renewcommand{\labelenumi}{(\theenumi)}   default
%\renewcommand{\labelenumi}{\theenumi.}    remove brackets
%------------------------------------------------


%------------ Course Information --------------------
\newcommand{\coursename}{Discrete Mathematics II}
\newcommand{\coursenum}{MACM 201 - D100 and D200}
\newcommand{\semester}{Fall 2020}
\newcommand{\instructor}{Jamie Mulholland and Michael Monagan}

%------------ Assignment Information -------------
\newcommand{\anum}{4}
\newcommand{\duedate}{Wednesday October 21, 2020}
\newcommand{\duetime}{11:59pm}

\pagestyle{fancy}
\fancyhf{} 

\lhead{\includegraphics[height=1cm]{logo.png}}
\rhead{\large\sc \coursenum ~~~~Assignment\ \#\anum}
\lfoot{ {\color{blue} \sc Copyright \instructor}}
\rfoot{{\small \thepage}}



%--------- Now for the document ----------------------------------

\begin{document}

\hfill{{\bf Due Date}:     \duedate, \duetime}

%\vspace{-0.75cm}
\subsection*{Instructions}


Answer all questions on paper or a tablet using your own handwriting.
Put your name, student ID number and page number at the top of each page.
If you use paper make a photo of each page and upload your solutions to crowdmark.
If you use a tablet, export your assignment to .pdf and upload the .pdf to crowdmark.

\begin{enumerate}
\item { \color{SFUred} \textbf{Textbook Reading} }  

	\begin{itemize}
	\item[$\bullet$] Sections: 10.2, 10.3
        \item[$\bullet$] DivAndConq.pdf notes (under Lecture Notes on Canvas)
        \end{itemize}

%=====================================
% Definitions, Concepts & Keywords
%=====================================
\item {\color{SFUred}\textbf{Definitions, Concepts \& Keywords}}

   \begin{itemize}
   \item[$\bullet$] Solve first order non-homogenous recurrences.
   \item[$\bullet$] Solve some second order non-homogenous recurrences.
   \item[$\bullet$] Understand the Mergesort algorithm.
   \item[$\bullet$] Solve recurrences arising from divide-and-conquer algorithms.
   \end{itemize}

\item {\color{SFUred}\textbf{Exercises}}

   \begin{enumerate}

   %=====================================
   % Textbook Questions
   %=====================================	
   \item  \textbf{Textbook Questions} 

        \begin{itemize}
        \item[]  Section 10.2 Exercise 24.
                 % Exercise 24 is a_n = a_{n-1} + 2 a_{n-2} which exercises 
                 % the characteristic polynomial two real roots case
        \item[]  Section 10.3 Exercises 1(b+d), 8.
        \end{itemize}


   \item \textbf{Questions}

   \begin{enumerate}

  \item Below is C code and Python code for an algorithm.

\medskip

C code:
\begin{verbatim}
  1:  void foo( int n, int A, int B, int C ) {
  2:     if( n==1 ) {
  3:         printf("%d to %d\n",A,B);
  4:         return;
  5:     }
  6:     foo( n-1, A, C, B );
  7:     printf("%d to %d\n",A,B);
  8:     foo( n-1, B, C, A );
  9:  }
\end{verbatim}

Python code:
\begin{verbatim}
  1:  def foo(n , A, B, C): 
  2:     if n==1: 
  3:         print A, "to", B
  4:         return
  5:
  6:     foo(n-1, A, C, B) 
  7:     print A, "to", B
  8:     foo(n-1, B, C, A)
\end{verbatim}

\medskip

    \noindent
    Let $H_n$ be the number of times the printing function is executed.
    Assume $n \ge 1$.
    Give a recurrence equation and an initial value for $H_n$ and solve it.
    Note, you do not need to know what the code is doing to answer this question.
    % H_n = 2 H_n-1 + 1, H_1 = 1, H_n = 2^n - 1

  \item  John takes out a bank loan for \$20,000 to buy a car.
         If the bank charges interest at 10\% per year, and John
         has to pay back the loan over 5 years, how much does he
         have to pay every year?  Use a recurrence.  See example 10.29.

  \item  Consider the complete bipartite graph $K_{n,n}$ with $2n$ vertices.
         Let $k_n$ be the number of edges in $K_{n,n}$.  
         Draw $K_{1,1}$, $K_{2,2}$ and $K_{3,3}$ and determine $k_1$, $k_2$, $k_3$.
         Give a recurrence relation for $k_n$ and solve it using an initial value.
         % k_n = k_n-1 + 2n - 1, k_1 = 1, k_2 = 4, k_3 = 9, k_n = n^2

  \item  Calculate a formula for $\sum_{i=0}^{n-1} (2i^2 + 3^i)$.
         % (n-1) n (2n-1)/3 + (3^n-1)/2

  \item  Solve the recurrence $a_n = 2a_{n-1} + 4^{n-1}$ with $a_1=3$.

  \item  Consider the recurrence $a_n - 3 a_{n-1} + 2 a_{n-2} = n$.
         \begin{itemize}
         \item[(a)] Find the general solution to the associated homogenous recurrence.
         \item[(b)]  Find a particular solution.
         \item[(c)] Find the solution for $a_0 = a_1 = 1$.
         \end{itemize}

  \item  Consider the recurrence $a_n - a_{n-1} - 6 a_{n-2} = 5 \cdot 3^n$.
         \begin{itemize}
         \item[(a)] Find the general solution to the associated homogenous recurrence.
         \item[(b)]  Find a particular solution.
         \item[(c)] Find the solution for $a_0=7$ and $a_1 = 5$.
         \end{itemize}


  \item The recurrence for number of comparisons that the Mergesort 
        algorithm does, assuming $n=2^k$, is $C(n) \le 2 \, C(n/2)+ n-1$ and $C(1)=0$.
        If the input array $A$ is already sorted, give a recurrence for the number of
        comparisons Mergesort does and solve it.  Hint: how many comparisons does
        the merging algorithm do?
        % C(n) = 2C(n/2) + n/2, C(1)=0, C(n) = n/2 log_2 n$.

  \item Consider the recurrence $T(n) = a T(n/b) + h(n)$ for $h(n)=An+B$ with
        initial value $T(1)=C$ where $a,b$ are positive integers with $b\ge 2$
        and $A,B,C$ are real numbers with $A\ge 0$ and $C \ge 0$.
        Using the method in the proof of Theorem 10.1 solve for $T(n)$.
        Simplify the formula for the case $a=1$ and for the case $a=b,b>1$.

   \item Consider the polynomials $f(x) = \sum_{i=0}^{n-1} a_i x^i$ and
         $g(x) = \sum_{i=0}^{n-1} b_i x^i$, both of degree $n-1$.
         In 1960 Karatsuba gave a new algorithm to multiply $f \times g$
         that does $T_n$ arithmetic operations where
         $ T_n = 3 T_{n/2} + n/2$ for $n\ge 2$ and $T_1 = 1$.
         Assume $n=2^k$ for some integer $k \ge 0$.
         Solve the recurrence for $T_n$ and then {\bf check} that your solution
         satisfies the recurrence.
         You should get an answer of the form $T_n = a n^{\log_2 3} + b n$
         where $a$ and $b$ are constants.  % a = 2, b = -1

\medskip \noindent
         Note, if you look up the Wikipedia page on Karatsuba's algorithm, you
         will see that Karatsuba first devised his the algorithm to multiply two $n$ 
         digit integers.  The same algorithm works multiplying two polynomials
         of degree $n-1$.  The recurrence is simpler in the polynomial case.

\end{enumerate}
\end{enumerate}

%\item {\color{SFUred}\textbf{ Selected Hints \& Answers}}
%
%Some final answers are given below. This is to provide you instant feedback on the validity of your solution - i.e. a quick check if your line of reasoning is correct. A complete solution requires full justification as to why these are the answers. 
%
\end{enumerate}

\bigskip

\begin{table}[h!]
\begin{center}
\begin{tabular}{ c c c }
$\ds \sum_{i=1}^n i = \ds \frac{n(n+1)}{2}$  &\quad  $\ds \sum_{i=1}^n i^2 = \ds \frac{n(n+1)(2n+1)}{6}$ & 
%$\ds \sum_{k=0}^{n} {n \choose k} = 2^n$     &\quad  $\ds \sum_{k=1}^n k {n \choose k} = \ds \frac{n}{2} 2^n$ \\
$\quad \ds \sum_{i=0}^{n-1} a^i = \ds \frac{a^n-1}{a-1} ~{\rm for}~ a \ne 1.$
\end{tabular}
\end{center}
\caption{Some useful sums}
\end{table}

\end{document}
