
\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, D200 and D300}
\newcommand{\semester}{Fall 2020}
\newcommand{\instructor}{Michael Monagan,Amarpreet Rattan,Mahsa Faizrahnemoon}

%------------ Assignment Information -------------
\newcommand{\anum}{3}
\newcommand{\duedate}{Monday February 8, 2021}
\newcommand{\duetime}{11:00 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
                 \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.
   
   \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
        
        \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 Insertionsort 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 Insertionsort( 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:     Insertionsort(A,n-1);
   6:     t = A[n-1];
   7:     for( i=n-2; i>=0 && A[i]>t; i-- )
   8:         A[i+1] = A[i];
   9:     A[i+1] = t;
  10:    }
\end{verbatim}}

\vspace{0.25cm}

Python Code:
{
\begin{verbatim}
   1: def Insertionsort(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:     InsertionSort(A,n-1)
   6:     t = A[n-1];
   7:     i = n-2
   8:     while i>=0 and A[i]>t:
   9:            A[i+1] = A[i]
   10:            i -= 1
  11:     A[i+1] = t\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 Consider $P_n$ the path graph on $n$ vertices.
Suppose vertices can be coloured red, green or blue.
Let $c_n$ be the number of ways the vertices in $P_n$ can be coloured such that no two adjacent vertices are coloured blue. 

\begin{itemize}
           \item[(a)] How many colourings are there for $P_1$, $P_2$, and $P_3$.
           \item[(b)] Find a recurrence for $c_n$.
           \item[(c)] Using the recurrence calculate $c_3$, $c_4$ and $c_5$.
\end{itemize}

   
  \item Solve the following recurrences for the given initial values

\begin{itemize}
  \item[(a)]  $a(n)=a(n-1)+2n \quad$  for $\quad n>1 \qquad a(1)=1$
  \item[(b)]  $a(n)=a(n-1)+(n-1)^2 \quad$  for $\quad n>1  \qquad a(1)=0$
\end{itemize}

  %\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 The first few $pentagol$ $ numbers$ are 1, 5, 12, and 22.

\includegraphics[height=5cm]{Pentagonal.png}

Find and solve a recurrence relation for the $n$th pentagonal number

\item Suppose there are $n$ different types of coupons in a bin. Assume there are equal number  of each coupon. If we draw coupons at random from the bin, how many draws will it take to get at least one of each coupon?

 % For the coupon collectors problem with $n$ coupons, let $T_n$ be the number of coupons we need to draw to get at least one of each coupon. 
%Calculate a table of values for $E[T_n]$ for $n$ in $\{1,2,3,4,5,6,8,10\}$.

\item In a card game
each player writes down 4 distinct cards from
a standard deck of 52 cards.
The dealer draws one card at random from the deck.  The player wins if they chose the card that the dealer drew.
\begin{itemize}
  \item[(a)] What is the expected number of times the player must play the game to win the game?  Use the geometric distribution.
% p = 4/52 = 1/13, E[T] = 1/p = 13.

  \item[(b)] If the player must pay 1 dollar to play the game and gets 10 dollars if they win the game, what is the expected winnings if the player plays the game 20 times.
% 1/13 x $10 x 20 - 12/13 x $1 x 20 = -$3.08.
\end{itemize}


\item  For any probability distibution, the sum of the probabilities must be 1.
Let $T$ be geometrically distributed with parameter $p$.
In class we showed that
$$\Pr(T = k) = p(1-p)^{k-1} \text{for} k \ge 1$$
and $E(T)=1/p$.  Show that the probabilities sum to 1.
% Solution - Maple sum syntax 😊
% sum( Pr(T=k), k=r(T) ) = sum( p(1-p)^(k-1), k=1..infinity )
% = p sum( q^(k-1), k=1..infinity ) where q=1-p
% = p sum( q^k, k=0..infinity ) = p/(1-q) = p/p = 1

%
%=======================================================
%=======================================================
%=========                              ================
%=========  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}
