% Review 2 problems
% Lecture 1  2 + 5 problems
% Lecture 2  2 + 4 problems
% Lecture 3+4  2 + 3 problems
% Total 2 + 7 + 6 + 5 = 20

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

\DeclareSymbolFont{extraup}{U}{zavm}{m}{n}
\DeclareMathSymbol{\varheart}{\mathalpha}{extraup}{86}
\DeclareMathSymbol{\vardiamond}{\mathalpha}{extraup}{87}
\newcommand{\red}{\color{red}}
\newcommand{\black}{\color{black}}

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

%------------ Assignment Information -------------
\newcommand{\anum}{2}
\newcommand{\duedate}{Monday February 1st, 2021}
\newcommand{\duetime}{11pm}

\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.
Please number each page.  
Include a cover page with your name, student ID number and a list of the
questions you have answered.

{\bf Do not upload my assignment to chegg.}  If you do and I catch
you I will fail you.  Michael Monagan.

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

		\begin{itemize}	
			\item Sections: 11.2, 3.4, 3.5, 3.6
                \end{itemize}


%=====================================
% Definitions, Concepts & Keywords
%=====================================
%\item {\color{SFUred}\textbf{Definitions, Concepts \& Keywords}}
%%\textbf{Definitions, Concepts \& Keywords}:
%
%\begin{itemize}
%\item[$\bullet$] Understand more terminology for graphs and trees.
%\item[$\bullet$] Know when two paths, cycles, graphs, and trees are not the same.
%\item[$\bullet$] Can calculate basic probabilities for discrete events.
%\end{itemize}

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

\begin{enumerate}

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

        \begin{itemize}
        \item[]  Section 11.1 Exercise 10. % 5 on Fall 2020 put #5 on the review
        \item[]  Section 11.2 Exercise 9.  % 12(b) on Fall 2020
                 One pair of graphs is isomorphic and the other pair
                 is not isomorphic.  For the isomorphic pair, 
                 give an isomorphism, that is, give a bijection
                 from the vertices of the first graph to the second.
        \item[]  Section 3.4 Exercises 7 and 12. % put #9  on the review
        \item[]  Section 3.5 Exercises 2 and 12 (omit $Pr(A \, \triangle \, B)$).  % #10 on F20 put #2 on review
        \item[]  Section 3.6 Exercises 2 and 8. % #14 is below. put #10 on the review
        \end{itemize}


   \item \textbf{Instructors Questions}

   \begin{enumerate}
%   \item How many ways can 6 people be seated at a circular table? \\
%         What if two people insist on sitting next to each other?
% These are from Lectures 5 and 6 on Graphs
   \item For a positive integer $n$, what
         is the value of the counter after the following code has been executed. (Both C and Python code are included, use the language you are familiar with.)
\medskip

%\begin{minipage}[t]{8cm}
%C code:
%\begin{verbatim}
%int i,j,k,counter;
%counter = 0;
%for( i=1; i<=n; i++ )  
%    for( j=1; j<=i; j++ ) 
%        for( k=1; k<=j; k++ )
%            counter ++;
%\end{verbatim}
%\end{minipage}
%\begin{minipage}[t]{5cm}
%python code:
%\begin{verbatim}
%counter = 0
%for i in range(1,n+1): 
%    for j in range(1,i+1):
%        for k in range(1,j+1):
%            counter = counter + 1
%\end{verbatim}	
%\end{minipage}

% The above is all values 1 <= i <= j <= k <= n.  This is combinations
% of size 3 from 20 with repetition so binomial(n+3-1,3).  For n=20 this is 1540
% Below it is all values 1 <= i < j < k <= n so combinations with no 
% repetitions so binomial(n,3).  For n=20 this is 1140.

\begin{minipage}[t]{8cm}
C code:
\begin{verbatim}
 int i,j,k,counter;
 counter = 0;
 for( i=1; i<=n; i++ )  
    for( j=1; j<i; j++ ) 
        for( k=1; k<j; k++ )
            counter ++;
\end{verbatim}
\end{minipage}
\begin{minipage}[t]{5cm}
python code:
\begin{verbatim}
 counter = 0
 for i in range(1,n+1): 
    for j in range(1,i):
        for k in range(1,j):
            counter = counter + 1
\end{verbatim}	
\end{minipage}

\medskip

   \item Consider the graph $G$ with vertices $V=\{1,2,3,4,5,6\}$ and \\
         edges $E=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{2,4\}\}$.
         \begin{enumerate}
         \item Draw $G$.
         \item Is $G$ bipartite?  Explain.
         \item List all spanning subgraphs of $G$ that are trees.
         %\item Draw the subgraph of $G$ induced by the vertices $\{1,2,3,4\}$.
         \end{enumerate}
    %\item Up to isomorphism, find all unlabelled graphs on 5 vertices with 5 edges.
    \item Up to isomorphism, find all unlabelled graphs on 5 vertices with 4 edges. \\
          You should get six graphs.  Identify which of your graphs are trees.
    %\item For each of the following draw two non-isomorphic graphs with 6 vertices where 
    %     \begin{enumerate}
    %      \item every vertex has degree 2
    %      \item every vertex has degree 3
    %     \end{enumerate}
    \item Read Definition 11.12 for the complement $\bar G$ of a graph $G$ 
          on page 523 of the textbook.
          \begin{enumerate}
          \item Draw the complement of $K_{1,1}$, $K_{2,2}$, and $K_{3,3}$.
          \item Find a subgraph $G$ of $K_4$ that is isomorphic to $\bar G$.
          %\item Find a subgraph $G$ of $K_5$ that is isomorphic to $\bar G$.
          \item Why can't $K_6$ have a subgraph $G$ that is isomorphic to $\bar G$?
          \end{enumerate}
    \item Let $n$ and $k$ be integers with $3 \le k \le n$. \\
         How many cycles of length $k$ are there in the complete graph $K_n$?
         %Hint: we can select a cycle of length $k$ from $K_n$ by choosing a sequence 
         %of $k$ distinct vertices $v_1, v_2, \ldots, v_k$ and then selecting the
         %cycle with vertex set $\{ v_1, \ldots, v_k \}$ and edge set \\
         %$\{ \{ v_1, v_2\}, \ldots, \{v_{k-1}, v_k \}, \{v_k, v_1 \} \}$.
         %It will help to determine (to avoid over-counting) for each cycle 
         %of length $k$ how many sequences select this cycle.
    %\item How many subgraphs of $K_n$ are isomorphic to $K_{1,4}$?
    %\item How many subgraphs of $K_n$ are isomorphic to $K_{3,7}$?
    %\item How many subgraphs of $K_{n,n}$ are isomorphic to $K_{3,7}$?
    %\item How many subgraphs of $K_n$ are isomorphic to $K_{2,5}$? \\
    %      How many subgraphs of $K_{n,n}$ are isomorphic to $K_{2,5}$?
    \item  \begin{enumerate}
           \item For $n \ge 6$ how many subgraphs of $K_n$ are isomorphic to $K_{2,4}$?
           \item For $n \ge 4$ how many subgraphs of $K_{n,n}$ are isomorphic to $K_{2,4}$?
           \end{enumerate}

\newpage
    \item Shown in the figure below are all (unlabelled) graphs on 4 vertices.
\medskip
\begin{center}
          \includegraphics[width=6cm]{graphs4.png}
\end{center}
\medskip
          The number of subgraphs of $K_n$ isomorphic to the graph 2 is $n \choose 2$ since
          every pair vertices in $K_n$ with an edge between them gives one subgraph
          of $K_n$ isomorphic to graph 2.
          \begin{enumerate}
          \item How many subgraphs of $K_n$ are isomorphic to graph 4?
          \item How many subgraphs of $K_n$ are isomorphic to graph 9?
          \end{enumerate}
          
    %% Use this for a test perhaps
    %\item Let $n \ge 3$ and let $G_n$ be a graph with vertex set 
    %        $\{x_1, \ldots, x_n\} \cup \{y_1, \ldots, y_n\}$ and the following edges:
    %    \begin{itemize}
    %    \item $\{x_1, x_2\}, \{x_2, x_3\}, \ldots, \{x_{n-1}, x_n \}, \{x_n, x_1\}$, 
    %    \item $\{y_1, y_2\}, \{y_2, y_3\}, \ldots, \{y_{n-1}, y_n \}, \{y_n, y_1\}$, and
    %    \item $\{ x_1, y_1 \}, \{x_2, y_2\}, \ldots, \{x_n, y_n\}$
    %    \end{itemize}
    %    \begin{enumerate}
    %    \item Draw the graph $G_3$
    %    \item How many edges are in $G_n$?
    %    \item How many paths of length 2 are in the graph $G_n$?
    %    \item For $n \ge 5$ how many cycles of length 4 are in the graph $G_n$?
    %    \end{enumerate}

    %\item We say that two distinct edges in a graph are \textbf{adjacent}
    %      if there is a vertex incident to both (the two edges share exactly one vertex.)
    %      For the graph $K_n$, determine the number of sets of two 
    %      edges $\{e, f\}$ with the property that $e,f$ are
    %      \begin{enumerate}
    %      \item adjacent and % Any 3 vertices: C(n,3)
    %      \item not adjacent. % Any 4 vertices: C(n,4)
    %      \end{enumerate}

% Section 3.4--3.6
          %\item  Suppose 6 men and 6 women attend a party. \\
          %       The host wants to select some of the 12 guests to play a game.
          %       \begin{itemize}
          %       \item[(a)] If the host chooses two guests at random, what is
          %       the probability of choosing two women?
          %       % C(6,2)/C(12,2) = 15/66
          %       \item[(b)] If the host chooses two guests at random, what is
          %       the probability of choosing one man and one woman?
          %       % There are C(12,2) pairs and 6*6 choices so 36/66 = 5/11
          %       \item[(c)] If the host chooses four guests at random, what
          %       is the probability of choosing two women and two men?
          %       You should get 5/11.
          %       % There are C(6,2)^2 choices out of C(12,4).
          %       % The probability is 5/11
          %       \end{itemize}
          \item  Suppose 6 men and 6 women are invited by a host to a dinner party. \\
                 Suppose the host selects 4 of the 12 guests at random for a game.
                 \begin{enumerate}
                 \item What is the probability the host chooses two men and two women?
                 % C(6,2)xC(6,2)/C(12,4) = 5/11
                 \item What is the probability the host chooses one man and three women?
                 % C(6,1)xC(6,3)/C(12,4) = 8/33
                 %\item What is the probability the host chooses no men and four women?
                 \end{enumerate}
                 Do this by defining the sample space $S$ and calculating
                 $\Pr(A) = |A|/|S|$ where $A$ is the set of considered outcomes.
          \item  A standard deck of 52 cards has 13 kinds of cards
                 labelled $A,K,Q,J,10,9,8,7,6,5,4,3,2$ in 
                 each of four suits $\red \varheart$ (hearts), $\red \vardiamond$ (diamonds)
                             $\clubsuit$ (clubs) and $\spadesuit$ (spades).
                 In the game of poker a player is dealt 5 cards from a standard deck of cards.
              \begin{enumerate}
              \item What is the probability of being dealt 5 cards from one suit? \\
                          For example,
                          $\red 2 \varheart, 7 \varheart, 9 \varheart, J \varheart, K \varheart$
              \item What is the probability of being dealt a pair? \\
                         An example of a pair is \  
          $\red J \varheart, 7 \vardiamond, 9 \varheart, \black 9 \spadesuit, K \clubsuit$
              \item What is the probability of being dealt two pairs? \\
                         An example of two pairs is \ 
          $\red 7 \varheart, 7 \vardiamond, 9 \varheart, \black 9 \spadesuit, K \clubsuit$
              %\item What is the probability of being dealt five different kinds of cards? \\
              %           An example of such a poker hand is
              %$\red 7 \varheart, 8 \vardiamond, 9 \varheart, \black J \spadesuit, K \clubsuit$
              \end{enumerate}

          %\item  At a university there are 300 first year computing majors.
          %       Suppose 100 can program in Python, 60 can program in Java, 80 can
          %       program in C++, 20 can program in Python and Java,
          %       20 can program in Java and C++, 10 can program
          %       in Python and C++ and none can program in all three languages.
          %    \begin{itemize}
          %       \item[(a)] If a student is selected at random, what is the probability
          %       that they can program in exactly 2 languages.
          %       % (20+20+10)/300 = 1/6
          %       \item[(b)] If a student is selected at random, what is the probability
          %       that they can only program in Python?
          %       % (100-10-20)/300 = 70/300 = 7/30
          %       \item[(c)] If two students are picked at random, what is
          %       the probability they can both program in Java?
          %       % C(100,2)/C(300,2)
          %    \end{itemize}
          %       Hint: use a Venn diagram.

          \item  Let $S$ be a finite sample space and $A$, $B$ and $C$ be
                 subsets of $S$.  
                 In class we showed that the $Pr(A \cup B) = Pr(A)+Pr(B)-Pr(A \cap B).$
                 % Answer is Theorem 3.9 note
                 Generalize this to find a formula for $Pr(A \cup B \cup C)$.
                 %\item[(b)] 
                 %           Let set $S = \{1,2,\dots,60\}$.
                 %           Using the formula from part (a), find the probability of 
                 %           choosing $x \in S$ that is divisible by 2 \textbf{or} 3 \textbf{or} 5.
                 %           You should get $11/15$.
                 %\end{itemize}
          \item  Let $S$ be a sample space and $A,B,C$ be events in $S$.
                 Use the result from the previous question to determine $\Pr(B)$ given
                 the following information
                 \begin{itemize}
                 \item $A$ and $B$ are independent,
                 \item $B$ and $C$ are independent,
                 \item $A$ and $C$ are disjoint, that is, $A \cap C = \emptyset$,
                 \item $\Pr( A ) = 1/5$,
                 \item $\Pr( C ) = 2/5$ and
                 \item $\Pr( A \cup B \cup C ) = 4/5$.
                 \end{itemize}
                 Hint: draw a Venn diagram with $A \cap C = \emptyset$.
          \item  A US company has developed an antibody test for whether a person
                 has had COVID.  If a person has had COVID, the probability that
                 the test is positive is 0.98.  If a person has NOT had COVID,
                 the probability that the test if positive is 0.02.
                 Suppose 10\% of Americans have had COVID.
                 Use Bayes' theorem to determine the probability that 
                 an American who tests positive has had COVID.

%
%=======================================================
%=======================================================
%=========                              ================
%=========  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. 
%
%%A2. $\binom{n}{1}\binom{n-1}{4}$ or equivalently $\binom{n}{1,4,n-5}$. Each come from a different way of solving the problem.\\
%A2. $\binom{n}{3}\binom{n-3}{7}$ or equivalently $\binom{n}{3,7,n-10}$. Each come from a different way of solving the problem. \\
%A3. $2\binom{n}{3}\binom{n}{7}$\\
%A4. $\binom{n}{2,3,n-5}$ \\
%A5. $nd^r$.\\
%A6. (b) $3n$ (c) $6n$

\end{enumerate}

\vspace{0.5cm}




\end{document}
