COMP2804: Discrete Structures II

Note: This is the webpage for the Fall 2020 offering of this course. It's only left here in case someone finds it useful as a reference.

Instructor: Pat Morin, 5177 HP,

Jump to Lecture Topics

Jump to the current lecture

Final Exam Information

The final exam will have the same format as the midterm exam, but will be 120 minutes long. It will be available on CULearn at the scheduled time. To find the scheduled time, consult the Final Exam Schedule but note that the final exam will be 120 minutes, not 180 minutes.

Learning Modality

Content for this course is delivered online, as a YouTube Live Stream on Mondays and Wednesdays at 10:00. I give lectures from a classroom in my basement that students can tune into at the scheduled time (see the lecture schedule below). During the lecture students are encouraged to ask questions using the YouTube chat feature. In addition to being available as a live stream, these lectures are left on YouTube, so they can be watched later.

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.

Important Dates

Sunday Sep 27 23:55 Assignment 1 due (in cuLearn)
Sunday Oct 11 23:55 Assignment 2 due (in cuLearn)
Wednesday Oct 21 16:00–17:30 Mid-term evaluation/exam
Sunday Nov 22 23:55 Assignment 3 due (in cuLearn)
Sunday Dec 6 23:55 Assignment 4 due (in cuLearn)


Assignments will be posted here as they become available.

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:


The midterm and final exams will take place online using cuLearn.

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

Here you can use use previous exams as practice exams.

Academic Integrity (New—Please Read)

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.

These are standard 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.

More information can be found at the ODS website

Grading Scheme

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


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:

Accommodation Statement

Carleton University is committed to providing access to the educational experience in order to promote academic accessibility for all individuals. Here is information on how to apply for academic accommodation.

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 Winter 2020 offering of COMP2804. Dates, videos, and topics will be updated as the course progresses.

Note: The entire collection of Fall 2020 lectures is available as a YouTube playlist

Note: If you want exactly the same material from a different lecturer, you can watch Michiel Smid's videos and I won't be offended.