
\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}{3}
\newcommand{\duedate}{Wednesday October 14, 2020}
\newcommand{\duetime}{11:59 pm}

\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}

\subsection*{Instructions}
Answer all questions on paper or a tablet using your own handwriting.
Please number each page.
Include a cover page with your name, student ID number and a list of
the questions you answered.
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 Section: 3.7 -- we will not cover variance 
			\item Sections: 10.1, 10.2 -- we will not cover Case B: Complex Roots
                \end{itemize}


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

   \begin{itemize}
   \item[$\bullet$] Random variables, expected value, the bins and balls problem.
   \item[$\bullet$] Construct and solve first order recurrence relations.
   \item[$\bullet$] Construct and solve second order recurrence relations.
   \end{itemize}

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

   \begin{enumerate}

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

        \begin{itemize}
        \item[]  Section 3.7 Exercise 2.
	\item[]  Section 10.1 Exercises 1, 2. % 3, 6
        \item[]  Section 10.2 Exercise 1(abd), 4.
        \end{itemize}

   \item \textbf{Instructors Questions}

   \begin{enumerate}
   \item Suppose John tosses a coin 5 times.
         Let $X$ be the number of heads. \\
         Calculate $Pr(X=x)$ for $x=0,1,2,3,4,5$ and find $E(X)$.
         % C(5,k)/2^k = 1/32, 5/32, 10/32, 10/32, 5/32, 1/32
         % E[X] = (0*1+1*5+2*10+3*10+4*5+5*1)/32 = 80/32 = 2.5
   \item \begin{itemize}
         \item[(a)] Let $X$ be a random variable and $a$ be a constant.
                    Show that $E(aX) = a E(X).$ \\
                    Follow the proof that $E(X+Y)=E(X)+E(Y)$ given in class.
         % E(aX) = sum( (aX)(s) Pr(s), s in S ) = sum( aX(s) Pr(s), s in S ) 
         %       = a sum( X(s) Pr(s), s in S ) = a E(X)
         \item[(b)] Let $X$ and $Y$ be two random variables.
                    Suppose we know $E(X)=7$ and $E(Y)=3$. \\
                    Let $Z=X-Y$ be a random variable.
                    What is $E(Z)$?  Justify your answer.
                    % E(Z) = E(X-Y) = E(X+(-Y)) = E(X)+E(-Y)
                    %      = E(X)+(-1) E(Y) E(X)-E(Y) = 7-3 = 4.
         \end{itemize}

   \item Suppose we toss 5 balls into 5 bins randomly.
         Let $X$ be the number of balls in a bin.
         \begin{itemize}
         \item[(a)] Determine the probability $X$ is 0, 1, 2, 3, 4, 5 balls.
         \item[(b)] Calculate $E(X)$.  You should get 1.
         \end{itemize}
         % > E := (m,n,k) -> binomial(m,k)*(1/n)^k*(1-1/n)^(m-k);
         % > seq( E(5,5,k), k=0..5 );                                             
         %                 1024  256  128  32
         %                 ----, ---, ---, ---, 4/625, 1/3125
         %                 3125  625  625  625
         % > evalf(%,5);                                                        
         %     0.32768, 0.40960, 0.20480, 0.051200, 0.0064000, 0.00032000
         % add( E(5,5,k), k=0..5 ) = 1


   \item Suppose we toss $m$ balls into $n$ bins randomly. \\
         Let $X$ be the expected number of empty bins. \\
         In class we showed that $E(X) = n (1-1/n)^m$.
         For $n=10$ and $m=5,10,20$ calculate $E(X)$. \\
         For the case $n=10$ and $m=20$, interpret the result for $E(X)$
         (write one sentence in English to explain what the result means).

   \item Suppose we toss $m$ balls into $n$ bins randomly.
         Let $X$ be the number of bins with exactly {\bf one} ball in them.
         Determine a formula for the probability $p$ that a bin has one ball in it
         and then calculate $E(X)$, the expected number of bins with one ball.
         For $m=n=10$ calculate $p$ and $E(X)$.  You should get $p=0.38742$.

   \item Consider the recurrence $a_{n+1} = 3 a_n - a_{n-1}$ with $a_1 = 1$, $a_2 = 1$.
         Calculate $a_0,a_3,a_4$.
         % a3 = 3a2-a1 = 3-1=2
         % a4 = 3a3-a2 = 6-1=5
         % a5 = 3a4-a3 = 15-2=13
         % a2 = 3a1-a0 => a0 = 3a1-a2 = 3-2=2.

   \item  Give an example of a first order non-homogenous recurrence relation
          and a second order homogeneous recurrence relation.

   \item  As I write this the number of people in India with the
          corona virus is 2.5 million.  It is estimated that each person
          who has the virus will, on average, infect 3 people in
          a week before recovering or dying.
          Let $i_n$ be the number of people infected
          after $n$ weeks where $i_0 = 2.5$ million.
          Give a recurrence relation for $i_n$.
          How long will it take before 100 million are infected?

\newpage
  \item Below is C code, and Python code, for the Selectionsort algorithm.
        The input is an array $A$ of $n$ decimal numbers.
        Line 10 sorts the first $n-1$ numbers in $A$ recursively.

\vspace{0.25cm}

C Code:
{
\begin{verbatim}
   1: void Selectionsort( double A[], int n ) {
   2: // sort A[0],A[1],...,A[n-1] into ascending order
   3:    int i,m; double t;
   4:    if( n<=1 ) return; // A is already sorted
   5:    m = 0;
   6:    for( i=1; i<n; i++ )
   7:       if( A[i]>A[m] ) m = i;
   8:    // interchange A[i] and A[m]
   9:    t = A[i]; A[i] = A[m]; A[m] = t;
  10:    Selectionsort(A,n-1);
  11:    return;
  12: }
\end{verbatim}
}

\vspace{0.25cm}

Python Code:
{
\begin{verbatim}
   1: def Selectionsort(A,n):
   2:     # sort A[0], A[1], ..., A[n-1] into ascending order
   3:     if n<=1: 
   4:         return # A is already sorted
   5:     m=0
   6:     for i in range(1,n):
   7:         if A[i]>A[m]: m=i
   8:     # interchange A[i] and A[m]
   9:     A[i], A[m] = A[m], A[i]
  10:     Selectionsort(A,n-1)\end{verbatim}
}

    Let $c_n$ be the number of comparisons between elements of $A$
    made in line 7.  Give a recurrence equation and an initial value
    for $c_n$ and solve it.  
    % c_n = (n-1) + c_{n-1}, c_1=0, c_n = n(n-1)/2.
    Does Selectionsort do fewer or more comparisons than Bubblesort? \\
    % The same!
    {\bf Note}: you do not need to know
    how an algorithm works in order to count the number of times
    it executes a particular operation.

   \item  In a resort in Mexico guests may have dinner at three restaurants,
       the Italian restaurant, the French restaurant or the Brazilian restaurant.
       Each evening you must eat at one of the restaurants 
       but you may not eat at the French restaurant two nights in a row.
       Let $d_n$ be the number of ways you may eat at the three
       restaurants over $n$ evenings.
       \begin{itemize}
       \item[(a)] How many eating choices are there for 1, 2 and 3 nights?
       % d1=3, d2=8, d3=22
       \item[(b)] Find a recurrence for $d_n$.
       % a_{n+1} = 2a_n + 2a_{n-1}
       \item[(c)] Using the recurrence relation, calculate $d_3, d_4$ and $d_5$.
       % a3 = 2 a2 + 2 a1 = 2x8+2x3 = 22
       % a4 = 2 a3 + 2 a2 = 2x22 + 2x8 = 60
       % a5 = 2 a4 + 2 a3 = 2x60 + 2x22 = 164
       \end{itemize}

  \item Consider the recurrence relation $a_n = a_{n-1} + An + B$ where
        $A$ and $B$ are constants.
        Solve the recurrence with $a_1 = 1$.

  %\item  Consider the recurrence relations and possible solutions.
  %       \begin{itemize}
  %       \item[(a)] $a_n = 2 a_{n-1} + 1$  and
  %       \item[(b)] $a_n - 3 a_{n-1} + 2 a_{n-2} = 0$.
  %       \end{itemize}
  %       \begin{itemize}
  %       \item[(1)] $a_n = 2^n+1$
  %       \item[(2)] $a_n = 2^n-1$
  %       \item[(3)] $a_n = 2^{n+1}-1$
  %       \end{itemize}
  %       Match the solutions with the recurrence relations.
         
  \item  Solve the recurrence 
         $x_n = x_{n-1} + 20 x_{n-2}$ for $n \ge 2$ with $x_0=5, x_1=-2$.


%
%=======================================================
%=======================================================
%=========                              ================
%=========  Selected Hints and Answers  ================
%=========                              ================
%=======================================================
%=======================================================
\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}
\end{document}
