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

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

Official Course Outline: Official course outline

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

Jump to Lecture Topics

Jump to Next Lecture Topic

News and Announcements

New (Sep 12): Here is a Sample first page from one of the upcoming quizzes. Print this and practice entering your student number so that you do it correctly during the quiz. Doing this incorrectly will result (at best) in a delay in receiving your grade or (at worst) no record of you having completed the quiz.

New (Sep 8): Assignment 1 has been updated with a few questions related to Lecture 2.

New (Sep 4): Assignment 1 has begun. It currently contains a question to expand your understanding of the first lecture, on Ramsey's Theorem. More questions will be added after each lecture.

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 in-class exams will take place, um, 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

In-class exam dates and the lecture schdule are in the Course Outline

Assignments

The four assignments in this course are optional and you don't need to submit them, but it is highly recommended that you make a serious attempt at each assignment. They are designed and the due dates are set so that they prepare you for each of the in-class 80 minute quizzes.

After the posted due date for each assignment (typically a week before the corresponding in-class quiz), I will post sample solutions for the assignment. Compare these to your solutions and learn where you went wrong. This is also part of preparing for the in-class quiz.

Each assignment will be posted here when it is ready.

• Assignment 1 has begun. More questions will be added after each lecture.

Exams

There will be four in-class quizzes (see the schedule in the course ouline). 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

The grading scheme appears in the course outline.

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) (in-class notes)
  • 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.
    

• Midterm Exam Preparation (sample midterm)

• Midterm Exam

• 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: (in-class notes)

  • Random variables, Section 6.1.
  • Independent random variables, Section 6.2.
  • Expected value, Section 6.4.
  • Linearity of expectation, Section 6.5.
    

• Lecture 17: (in-class notes)

  • 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: (in-class notes)

  • Quick-Sort and random binary search trees, Section 6.10 and Section 7.1 of ODS.
    

• Lecture 19: (in-class notes)

  • 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 (in-class notes)

  • 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 (in-class notes)

  • Proof that the Ramsey Number $R(k,k)\le 2\cdot 4^k$
  • Planar graphs, Section 7.5.1
  • The crossing lemma, Section 7.5.2
    

• Final-exam review
  • Solving the Winter 2019 Final Exam
    
  • Solving questions 19-25 on the Winter 2019 Final Exam