**Instructor:** Pat Morin, 5177 HP, morin@scs.carleton.ca

# Course Objectives

A second course that is designed to give students a basic understanding of Discrete Mathematics and its role in Computer Science. Computers handle discrete data rather than continuous data. The course presents an overview of some of the major theoretical concepts needed to analyze this type of data.

# Office Hours

Day | AM/PM | Staff | Time | Location |
---|---|---|---|---|

Monday | AM | Kirk Zhen | 8:30-10:30 | 4125 Herzberg |

Monday | PM | Xiaoying Liu | TBA | 4125 Herzberg |

Tuesday | AM | Pat Morin | 9:00-11:00 | 5177 Herzberg |

Tuesday | PM | Abdullah Alchihabi | 2:40-4:40 | 4125 Herzberg |

Wednesday | AM | Shelly Wang | 10:00-12:00 | 4125 Herzberg |

Wednesday | PM | Alexander Johns | 2:40-4:40 | 4125 Herzberg |

Thursday | AM | Alexa de Grandmont | 9:00-11:00 | 4125 Herzberg |

Thursday | PM | FX CC | 1:30-3:30 | 4125 Herzberg |

Friday | AM | Zoltan Kalnay | 9:00-11:00 | 4125 Herzberg |

Friday | PM | Mehrnoosh Javarsineh | 13:00-15:00 | 4125 Herzberg |

# Important Dates

Sunday | Sep 22, 23:55 | Assignment 1 due (in cuLearn) |

Sunday | Oct 13, 23:55 | Assignment 2 due (in cuLearn) |

Sunday | Nov 17, 23:55 | Assignment 3 due (in cuLearn) |

Friday |
Dec 6, 23:55 | Assignment 4 due (in cuLearn) |

Thursday | Oct 17 | Mid-term exam for Section A (in class) |

Friday | Oct 18 | Mid-term exam for Section B (in class) |

# Sample Exams

Here are some sample final and midterm exams that you can use to study from.

## Final Exams

- Final exam Winter 2019 with solutions
- Final exam Fall 2018 with solutions
- Final exam Winter 2018 with solutions
- Final exam Fall 2017 with solutions
- Final exam Winter 2017 with solutions
- Final exam Fall 2016 with solutions
- Final exam Fall 2015 with solutions
- Final exam Winter 2015 with solutions
- Final exam Fall 2014 with solutions
- Final exam Winter 2014 with solutions
- Final exam Fall 2013 with solutions

## Midterm Exams

- Midterm exam Fall 2019 Section A
- Midterm exam Fall 2019 Section B
- Midterm exam from Fall 2015 with answers
- Midterm exam from Fall 2018 with answers
- Midterm exam from Winter 2019 with answers

# Assignments

- Assignment 4 was due on Friday December 6, before 23:55. Sample solutions for Assignment 4 are now available as a PDF file that was created from this LaTeX file.
- Assignment 3 was due on Sunday November 17, before 23:55. Sample solutions for Assignment 3 are now available as a PDF file that was created from this LaTeX file.
- Assignment 2 was due on Sunday October 13th, before 23:55. Sample solutions for Assignment 2 are available as a PDF file
- Assignment 1 was due on Sunday September 22nd, before 23:55. Sample solutions for Assignment 1 are now available as a PDF file that was created from this LaTeX file. For study purposes, here are two similar assignments (with solutions) from Fall 2018 and Winter 2019

Please note the following rules and requirements about assignments:

- Late assignments will not be accepted.
- You can type your solutions, or write them by hand and scan them (for example, using a scan app on your phone or using a real scanner).
- Solutions written-up in LaTeX are preferred, but not strictly required. In case you want to learn LaTeX, here is a tutorial. Learning LaTeX is a useful exercise, since many programs (including Microsoft Word) now use LaTeX for typesetting formulas.
- Each assignment must be submitted as one single PDF file through cuLearn.

# Grading Scheme

Assignments | 25% |

Mid-term exam | 25% |

Final exam | 50% |

# Textbooks

We will be using the following free (*libre* and *gratis*) textbooks. The first one is the primary textbook for this course. The second contains supplementary and background material:

- Michiel Smid. Discrete Structures for Computer Science: Counting, Recursion, and Probability, 2019.
- Eric Lehman, F Thomson Leighton, and Albert R Meyer. Mathematics for Computer Science, 2018

# Accommodation Statement

The Paul Menton Centre for Students with Disabilities (PMC) provides services to students with Learning Disabilities (LD), psychiatric/mental health disabilities, Attention Deficit Hyperactivity Disorder (ADHD), Autism Spectrum Disorders (ASD), chronic medical conditions, and impairments in mobility, hearing, and vision. If you have a disability requiring academic accommodations in this course, please contact PMC at 613-520-6608 or pmc@carleton.ca for a formal evaluation. If you are already registered with the PMC, contact your PMC coordinator to send me your Letter of Accommodation at the beginning of the term, and no later than two weeks before the first in-class scheduled test or exam requiring accommodation (if applicable). Requests made within two weeks will be reviewed on a case-by-case basis. After requesting accommodation from PMC, meet with me to ensure accommodation arrangements are made. Please consult the PMC website (www.carleton.ca/pmc) for the deadline to request accommodations for the formally-scheduled exam (if applicable).

# Lecture topics

You should already be familiar with the following topics from COMP 1805: basic logical reasoning, sets and functions, proof strategies (direct proof, proof by contradiction, proof by induction), Sigma-notation for summations, basic graph theory, Big-Oh, Big-Omega, Big-Theta. You may take a look at Chapter 2 of the textbook and do some of the exercises at the end of that chapter. Review the relevant parts of Lehman et al if you are still struggling.

- Sep 4/5: Introduction
- Course overview.
- Chapter 1 in the textbook: Ramsey Theory,
~~Sperner's Theorem,~~Quick-Sort.

- Sep 6: Pigeonhole sampler
- Theorems 3.1-3.5 in $12^2$ beautiful mathematical theorems with
short proofs

- Theorems 3.1-3.5 in $12^2$ beautiful mathematical theorems with
short proofs
- Sep 10/11: Counting (1)
- Product Rule, Bijection Rule, Sections 3.1, 3.2.

- Product Rule, Bijection Rule, Sections 3.1, 3.2.
- Sep 12/13: Counting (2)
- Complement Rule, Sum Rule, Inclusion-Exclusion, permutations, binomial coefficients, Sections 3.3, 3.4, 3.5, 3.6.

- Complement Rule, Sum Rule, Inclusion-Exclusion, permutations, binomial coefficients, Sections 3.3, 3.4, 3.5, 3.6.
- Sep 17/18: Counting (3)
- Binomial coefficients, Newton's Binomial Theorem, combinatorial proofs,
Vandermonde's Identity, Pascal's Triangle, Sections 3.6, 3.7.

- Binomial coefficients, Newton's Binomial Theorem, combinatorial proofs,
Vandermonde's Identity, Pascal's Triangle, Sections 3.6, 3.7.
- Sep 19/20: Counting (4)
- Sections 3.7 and 3.8.
- How many strings can be obtained from MISSISSIPPI, counting solutions of linear equations, Section 3.9.

- Sep 24/25: Pigeonhole Principle
- Section 3.10
- Excercise 3.84.

- Sep 26/27: Recursion (1)
- Recursive functions, Section 4.1.
- Fibonacci numbers, Section 4.2.
- Counting 00-free bitstrings
- Counting $aa$-free strings over $\{a,b,c\}$
- Counting $ab$-free strings over $\{a,b,c\}$

- Oct 1/2: Recursion (2)
- Proof that $f_n = (\varphi^n - \psi^n)/\sqrt{5}$
- Euclid's algorithm, Section 4.5.

- Oct 3/4: Recursion (3)
- MergeSort, Section 4.6.

- MergeSort, Section 4.6.
- Oct 8/9: Randomization and probability
- Anonymous broadcasting: Dining Cryptographers, Section 5.1.
- Probability Theory: Probability spaces, sample spaces, probability functions, Section 5.2.
- Basic rules of probability, Section 5.3.

- Oct 10/11:
- Finishing up Section 5.3
- Uniform probability spaces, Section 5.4.
- Exercise 5.11, which is known as the Newton–Pepys problem.

- Oct 15/16:
- Midterm review and slack time

- Midterm review and slack time
- Oct 17/18:
- Midterm exam

- Oct 29/30:
- The Birthday Paradox (section 5.5)
- Find the big box (section 5.6)

- Oct 31/Nov 1:
- Let's Make a Deal, the Monty Hall Problem, Section 5.7.
- Conditional probability, Section 5.8.
- Anil's kids, Exercise 5.40, the remarkable set B.

- Nov 5/6:
- Independent events, Section 5.11.
- Exercise 5.81.

- Nov 7/8:
- Section 5.12, in particular, the probability of a circuit failing, Section 5.12.3.
- Choosing a random line in a file, Section 5.13.

- Nov 12/13:
- Infinite probability spaces, Section 5.15, Exercises 5.85 and 5.91.
- The law of total probability

- Nov 14/15:
- Random variables, Section 6.1.
- Independent random variables, Section 6.2.
- Expected value, Section 6.4.
- Linearity of expectation, Section 6.5.

- Nov 19/20:
- Indicator random variables, Section 6.8, Exercise 6.57.
- Expected running time of Insertion-Sort, Section 6.9
- Largest elements in prefixes of random permutations, Section 6.8.2.

- Nov 21/22:
- Estimating the harmonic number, Section 6.8.3.
- Expected running time of Quick-Sort, Section 6.10.

- Nov 28/29:
- Geometric distribution and its expected value, Section 6.6, Exercise 6.35.
- Exercise 6.59 (the Coupon Collector's Problem)
- Binomial distribution and its expected value, Section 6.7.

- Nov 26/27: The Probabilistic Method
- Finding large bipartite subgraphs, Section 7.1
- Graphs with no large clique or independent set, Section 7.2
- Jaccard distance satisfies triangle inequality, Section 7.4

- Dec 3/4: Exam review
- Solving the Winter 2019 Final Exam

- Solving questions 19-25 on the Winter 2019 Final Exam

- Solving the Winter 2019 Final Exam
- Dec 5/6:
- No class (for either section)