
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

We have lots of office hours during which TAs or myself can help you with studying course material and offer you guidance for assignments.

Day Staff Time Location
Mon AM Yuan Wu 09:00-11:00 4125 Herzberg
Mon AM Zoltan Kalnay 11:00-13:00 4125 Herzberg
Mon PM Mehrnoosh Javarsineh 14:00-16:00 4125 Herzberg
Tue AM Pat Morin 09:00-11:00 5177 Herzberg
Tue PM Alexa de Grandmont 14:30-16:30 4125 Herzberg
Wed AM Andy Tran 11:30-13:00 4125 Herzberg
Wed PM Abdullah Alchihabi 15:30-17:30 4125 Herzberg
Thu AM Mathieu Leblanc 09:30-11:30 4125 Herzberg
Thu PM Andy Tran 14:30-16:00 4125 Herzberg
Fri AM Hao Yan 10:00-12:00 4125 Herzberg
Fri PM FX CC 12:00-14:00 4125 Herzberg
Fri PM Joyce Bacic 16:00-18:00 4125 Herzberg

# Important Dates

Sunday Jan 26, 23:55 Assignment 1 due (in cuLearn)
Sunday Feb 9, 23:55 Assignment 2 due (in cuLearn)
Thursday Feb 13, 13:00 Mid-term exam (in class)

# Sample Exams

Here are exams for previous offerings of this course (for study purposes).

# Assignments

• Late assignments will not be accepted.
• I will not respond to
• 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.

As of 2020, there are new penalties in place for academic integrity violations. These will be issued by the Associate Dean (Undergraduate Affairs) of Science to students who copy, in whole or in part, work they submit for assignments.

• First offence: F in the course
• Second offence: One-year suspension from program
• Third offence: Expulsion from the University

These are minimum penalties. More-severe penalties will be applied in cases of egregious offences. Failure to inform yourself of the expectations regarding academic integrity is not a valid excuse for violations of the policy. When in doubt, ASK your instructor or TA.

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:

# 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.

The following schedule is from the Fall 2019 offering of COMP2804. Dates, videos, and topics will be updated as the course progresses.

• Jan 7: Introduction
• Course overview.
• Chapter 1 in the textbook: Ramsey Theory, Sperner's Theorem, Quick-Sort.
• Jan 9: Counting (1)
• Product Rule, Sections 3.1
• Jan 14: Counting (2)
• Bijection Rule, Complement Rule, Sum Rule, The Principle of Inclusion-Exclusion, Sections 3.2, 3.3, 3.4, 3.5.
• Jan 16: Counting (3)
• Binomial coefficients, Newton's Binomial Theorem, combinatorial proofs, Vandermonde's Identity, Pascal's Triangle, Sections 3.6, 3.7.
• Jan 21: Counting (4)
• Sections 3.7 and 3.8.
• How many strings can be obtained from SUCCESS? Section 3.9.1
• Counting solutions of linear (in)equalities, Section 3.9.2
• Jan 23: Pigeonhole Principle
• Simon's Drinking Problem, Section 3.10.1
• Every $(n+1)$-element subset of $\{1,\ldots,2n\}$ contains a divisible pair, Section 3.10.2
• Infinity of primes, Section 3.10.4
• Jan 28: Recursion (1)
• Recursive functions, Section 4.1.
• Fibonacci numbers, Section 4.2.
• Proof that $f_n = (\varphi^n - \psi^n)/\sqrt{5}$
• Counting 00-free bitstrings
• Counting $aa$-free strings over $\{a,b,c\}$
• Counting $ab$-free strings over $\{a,b,c\}$
• Jan 30: Recursion (2)
• Exercise 4.38
• Euclid's algorithm, Section 4.5. (gcd.py)
• Feb 4: Recursion (3)
• MergeSort, Section 4.6.

• Feb 6: 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.

• Feb 11:
• Midterm review
• Feb 13:
• Midterm exam

• 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
• 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
• Dec 5/6:
• No class (for either section)