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


\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}{2}
\newcommand{\duedate}{Wednesday September 30, 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.
{\bf Please number each page}
Include a cover page with your name, student ID number and a list of the
questions you have answered.

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

		\begin{itemize}	
			\item Sections: 11.1, 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 Exercises 5. % 10 is below
        \item[]  Section 11.2 Exercises 9(a), 12(b).
        \item[]  Section 3.4 Exercises 6, 9.
        \item[]  Section 3.5 Exercises 10 (omit $Pr(A \, \triangle \, B)$).
        \item[]  Section 3.6 Exercises 2, 8.
        \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}


%\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}
   \item Consider the graph $G$ with vertices $V=\{1,2,3,4,5\}$ and \\
         edges $E=\{\{1,2\},\{2,3\},\{3,1\},\{3,4\},\{4,5\},\{5,1\}\}$.
         \begin{enumerate}
         \item Draw $G$.
         \item How many cycles does $G$ have?  List them.
         \item Is $G$ bipartite?  Explain.
         \item Give a spanning subgraph of $G$ that is a tree.
         \item Draw the subgraph of $G$ induced by the vertices $\{2,4,5\}$.
         \end{enumerate}
    \item A graph $G=(V,E)$ is called regular if every vertex 
          in $G$ has the same degree.  Draw a graph with 6 vertices where
         \begin{enumerate}
          \item every vertex has degree 1
          \item every vertex has degree 2
          \item every vertex has degree 3
          \item every vertex has degree 4
         \end{enumerate}
    \item Up to isomorphism, find all unlabelled graphs on 5 vertices with 5 edges.  
    \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 Let $K_5^-$ be a graph obtained from $K_5$ by deleting one edge.  \\
          How many subgraphs of $K_n$ are isomorphic to $K_5^-$?
    %% 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[(a)] 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  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$.  
                 \begin{itemize} \item[(a)]
                 In class we showed that \\ $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  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.03.
                 Suppose 10\% of Americans have had COVID -- which will probably
                 be true by the time you are reading this.
                 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}
