COMP 2804 — Discrete Structures II

Carleton University, Fall 2026

Course Information

Instructor	Pat Morin
Term	Fall 2026
Course Website	https://patmorin.me/teaching/2804/

Description

A second course in discrete mathematics and discrete structures, covering counting, sequences and sums, discrete probability, basic statistics, recurrence relations, and randomized algorithms, illustrated through examples from computing.

Textbooks

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

Weekly Schedule

Week	Topic	Readings	Date
1	Introduction	Lecture 1, Ch. 1	Sep 7
2	Counting	Lectures 2–3, Sec. 3.1–3.5	Sep 14
3	Counting	Lectures 4–5, Sec. 3.6–3.9	Sep 21
4	Pigeonhole Principle (Test 1)	Lecture 6, Sec. 3.10	Sep 28
5	Recursion	Lectures 7–8, Sec. 4.1–4.5	Oct 5
6	Recursion (Test 2)	Lecture 9, Sec. 4.6	Oct 12
7	Discrete Probability	Lectures 10–11, Sec. 5.1–5.6	Oct 19
8	Conditional Probability	Lectures 12–13, Sec. 5.7, 5.8, 5.11	Nov 2
9	Probability	Lectures 14–15, Sec. 5.12, 5.13, 5.15	Nov 9
10	Random Variables (Test 3)	Lecture 16, Sec. 6.1–6.5	Nov 16
11	Random Variables	Lectures 17–18, Sec. 6.8–6.10	Nov 23
12	Geometric and Binomial Random Variables (Test 4)	Lecture 19, Sec. 6.6, 6.67	Nov 30
13	The Probabilistic Method	Lectures 20–21, Sec. 7.1–7.5	Dec 7

Assessment

Component	Weight	Date
In-class Test 1 (Counting)	12.5%	Sep 30
In-class Test 2 (Pigeonhole and Recursion)	12.5%	Oct 14
In-class Test 3 (Probability)	12.5%	Nov 18
In-class Test 4 (Random Variables)	12.5%	Dec 2
Final Exam	50%	TBA

A missed in-class test transfers its weight to the final exam.

Repository Structure

.
├── README.md
├── notes/          weekly lecture notes
├── assignments/    problem sets and solutions
├── tests/          practice and past in-class tests
└── exam/           final exam review material

Progress Log

Week	Topic	Status
1	Introduction
2	Counting
3	Counting
4	Pigeonhole Principle
5	Recursion
6	Recursion
7	Discrete Probability
8	Conditional Probability
9	Probability
10	Random Variables
11	Random Variables
12	Geometric/Binomial Random Variables
13	The Probabilistic Method