$\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{\mathbf{E}}\DeclareMathOperator{\deg}{deg}\newcommand{\N}{\mathbb{N}}$

Note: This is the webpage for the Fall 2024 offering of COMP2804, Sections A and B.

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

Jump to Next Lecture Topic

News and Announcements

New (Oct 11): Your midterm exam will take place in your class on Wednesday October 30th. Students in Section B will write their exam at 10:00am and students in Section A will write their exam at 4:00pm. The two exams are not the same.
If you write your exam at 10:00am, please don't discuss it with anyone (especially in a public forum) until after 5:00pm. Although the exams are not the same, some questions look similar but the question and/or answers have been changed slightly and need to be read carefully. If you are writing the 4:00pm exam, I advise you not to discuss the exam with anyone who took it at 10:00am. Any information you get by doing so is likely to result in you misreading a question or answer, causing you unnecessary confusion.

New (Oct 3): The notes I make for the afternoon class document camera are now available for most of the lecture topics.

New (Oct 2): There will be no COMP2804A class on Friday October 11th. There will be no COMP2804B class on Friday December 6th. The first cancellation is to prevent Section A from being two lectures ahead. The second cancellation is so that each section gets 24 lectures.

New (Sep 30): Assignment 2 is now available here. Contrary to the course outline, Assignment 2 is due on October 18, at 11:55pm.

New (Sep 30): Assignment 1 solutions (and grading guidelines) are now available here.

New (Sep 13): This course has course discord to communicate with other students.

Learning Modality

Classes will take place in a classroom somewhere on campus that I am not allowed to disclose. Find the location by logging into Carleton Central. The mid-term exam will take place in class. The final exam is a formally scheduled exam managed by exam services.

Below, you will find a class by class list of lecture topics along with videos of each topic recorded in Fall 2020. These can be a useful resource if, for some reason, you miss some classes.

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 Schedule

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

Important Dates

Due dates for assignments and the date of the midterm exam are in the Course Outline

Assignments

Assignments will be posted here as they become available. Assignments are to be submitted using Brightspace.

Assignment 3 is due on November 10th, at 11:55pm. It should be submitted on Brightspace as a single PDF file.
Assignment 2 is due on October 18th, at 11:55pm. It should be submitted on Brightspace as a single PDF file. Here are Assignment 2 sample solutions and grading guidelines.
Assignment 1 is due Sunday September 22nd, at 11:55pm. It should be submitted on Brightspace as a single PDF file. Here are Assignment 1 sample solutions and grading guidelines.

If you would like to see some sample solutions from a previous offering of this course, you can find some here. If you are looking for an example of excellent assignment solutions, here are the sample solutions (pdf) (tex) for Assignment 1 Fall 2019

Please note the following rules and requirements about assignments:

Late assignments will not be accepted.
Assignments emailed to me will not be accepted.
I will not respond to emails sent shortly before or after assignment deadlines asking for exceptions to the preceding two rules.
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 Brightspace.

Exams

The midterm exam will take place in class. The final exam will be a formally scheduled exam handled by examination services.

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

Here you can use use previous exams as practice exams.

Grading Scheme

This course will use the following grading scheme.


Assignments	25%
Mid-term exam	25%
Final exam	50%

If you fail to submit an assignment on time but are able to provide me with a valid reason then I will shift the weight of the missed assignment onto the remaining assignments. If you fail to submit all of the assignments with a valid reason for each one them then I will shift their weight onto the final exam. If you fail to attend the midterm exam and provide me with a valid reason then I will shift the weight of the midterm exam onto the final exam.

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

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.

Note: Most of the videos below are from the Fall 2020 offering of this course and are provided as a tool for reviewing things that will be taught in class. The lecture-by-lecture schedule may be changed as the semester progresses and (late in the semester) we may cover some topics not covered in the videos below.

Lecture 1: Introduction (in-class notes)
- Course overview.
- Chapter 1 in the textbook: Ramsey Theory, Quick-Sort, Sperner's Theorem.
Lecture 2: Counting (1) (in-class notes)
- Product Rule, Section 3.1
Lecture 3: Counting (2)
- Bijection Rule, Complement Rule, Sum Rule, The Principle of Inclusion-Exclusion, Sections 3.2, 3.3, 3.4, 3.5.
Lecture 4: Counting (3) (in-class notes)
- Binomial coefficients, Newton's Binomial Theorem, combinatorial proofs, Vandermonde's Identity, Pascal's Triangle, Sections 3.6, 3.7.
Lecture 5: Counting (4) (in-class notes)
- 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
Lecture 6: Pigeonhole Principle (in-class notes)
- 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
- The Erdös-Szekeres Theorem
- ~~Infinity of primes, Section 3.10.4~~
Lecture 7: Recursion (1) (in-class notes)
- 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\}$
Lecture 8: Recursion (2) (in-class notes)
- Exercise 4.38
- Euclid's algorithm, Section 4.5. (gcd.py)
Lecture 9: Recursion (3) (in-class notes)
- MergeSort, Section 4.6. (merge_sort.py)
Lecture 10: Randomization and probability (in-class notes)
- 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.
Lecture 11: Two surprising examples (in-class notes)
- The Birthday Paradox (section 5.5)
- Find the big box (section 5.6)

Lecture 12:
- Find Patti: The O'Reilley Triplets Problem, Section 5.7.
- Conditional probability, Section 5.8.
- Anil's kids, Exercise 5.40, the remarkable set B.
Exam Preparation (sample midterm)
Lecture 13: Independent events (in-class notes)
- Independent events, Section 5.11.
- Exercise 5.81: Annie, Boris, and Charlie write an exam.
Lecture 14: (in-class notes)
- 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.
Lecture 15: (in-class notes)
- Infinite probability spaces, Section 5.15, Exercises 5.85 and 5.91.
- The law of total probability
Lecture 16:
- Random variables, Section 6.1.
- Independent random variables, Section 6.2.
- Expected value, Section 6.4.
- Linearity of expectation, Section 6.5.
Lecture 17: (—)
- 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.
- Estimating the harmonic number, Section 6.8.3.

Lecture 18: (—)
- Quick-Sort and random binary search trees, Section 6.10 and Section 7.1 of ODS.
Lecture 19:
- 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.

Lecture 20: 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
Lecture 21: Planar graphs and the Crossing Lemma
- Planar graphs, Section 7.5.1
- The crossing lemma, Section 7.5.2
Lecture 22: Sperner's Theorem
- Sperner's Theorem (lower bound), Section 1.2
- Sperner's Theorem (upper bound), Section 7.3
Final-exam review
- Solving the Winter 2019 Final Exam
- Solving questions 19-25 on the Winter 2019 Final Exam