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

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

Jump to Lecture Topics

News and Announcements

New (Apr 25): Here is the final exam with answers.

New (Apr 12): Your final exam will be on Friday April 22 at 14:00 EDT (2:00pm). In order to access the exam you need to preregister by entering your student number in this form. Doing so will send an email to your Carleton email address with information on how to access your exam.

Please do this as soon as possible, well before the exam date.

New (Apr 7): There will be no in-person classes on Tuesday April 12. Watch the Final Exam Review lecture videos (below) instead.

New (Feb 28): The date and time for the final exam has been posted on the Scheduling and Examination Services website. Your final exam will take place online at this date and time, even if you live in a very different time zone.

Learning Modality

The in-person classes will take place in Southam Hall Theatre B. If you would like to be around other human beings, feel free to attend either (or both) of the in-person classes, even if you didn't register for an in-person section. The survey I did before reading week suggests that the number of students willing and able to attend in-person is well-below the limit for this classroom.

If you want to tune into these classes via Zoom, you can do so using the links available in the course Brightspace page. To be allowed into the meeting, you will have to be logged into Zoom.

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 will have lots of office hours during which TAs or myself can help you with studying course material and offer you guidance for assignments.

To meet with one of these people during their office hours just click on their name to open a Google Meet or Zoom link.

Important Dates

Sunday	Jan 30	23:55	Assignment 1 due (in Brightspace)
Sunday	Feb 13	23:55	Assignment 2 due (in Brightspace)
Thursday	Feb 17	16:00–17:30	Mid-term evaluation/exam
Sunday	Mar 20	23:55	Assignment 3 due (in Brightspace)
Sunday	Apr 10	23:55	Assignment 4 due (in Brightspace)

Note: If you are enrolled in Sections B or D and have a conflict with the midterm exam time, then please contact me as soon as possible. You will be allowed to write the midterm exam on the same day at 8:30-10:00 (am).

Assignments

Assignments will be posted here as they become available.

• Here is Assignment 4 and here are the Assignment 4 answers.
• Here is Assignment 3 and here are the Assignment 3 answers.
• Here is Assignment 2 and here are the Assignment 2 answers.
• Here is Assignment 1 and here are the Assignment 1 answers.

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 and final exams will take place online using Brightspace.

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

Here you can use use previous exams as practice exams.

Academic Integrity

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

This course will use the following grading scheme.

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

If you fail to submit an assignment and provide me with a valid reason then I will shift the weight of the missed assignment onto the remaining assignments. 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

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.

• Lecture 1: Introduction
  • Course overview.
  • Chapter 1 in the textbook: Ramsey Theory, Quick-Sort, Sperner's Theorem.
    
• Lecture 2: Counting (1)
  • 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)
  • Binomial coefficients, Newton's Binomial Theorem, combinatorial proofs, Vandermonde's Identity, Pascal's Triangle, Sections 3.6, 3.7.
    
    
• Lecture 5: 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
    
    
• Lecture 6: 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
  • The Erdös-Szekeres Theorem
  • Infinity of primes, Section 3.10.4
    
• Lecture 7: 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\}$
    
• Lecture 8: Recursion (2)
  • Exercise 4.38
  • Euclid's algorithm, Section 4.5. (gcd.py)
    
• Lecture 9: Recursion (3)
  • MergeSort, Section 4.6.
    
• Lecture 10: 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.
    
    
• Lecture 11 Watch on your own:
  • Midterm review using the Fall 2015 Midterm
    
• Lecture 12: Two surprising examples
  • The Birthday Paradox (section 5.5)
  • Find the big box (section 5.6)
  • Morning lecture video
  • Afternoon lecture video
    
    
• Oct 21: Midterm exam on cuLearn
• Lecture 13:
  • 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.
    
• Lecture 14:
  • Independent events, Section 5.11.
  • Exercise 5.81: Annie, Boris, and Charlie write an exam.
  • Morning lecture video
  • Afternoon lecture video
    
    
• Lecture 15:
  • 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.
  • Morning lecture video
  • Afternoon lecture video
    
• Lecture 16:
  • Infinite probability spaces, Section 5.15, Exercises 5.85 and 5.91.
  • The law of total probability
  • Morning lecture video
  • Afternoon lecture video
    
• Lecture 17:
  • Random variables, Section 6.1.
  • Independent random variables, Section 6.2.
  • Expected value, Section 6.4.
  • Linearity of expectation, Section 6.5.
  • Morning lecture video
  • Afternoon lecture video
    
• Lecture 18: (—)
  • 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.
  • Morning lecture video
  • Afternoon lecture video
    
    
• Lecture 19: (—)
  • Quick-Sort and random binary search trees, Section 6.10 and Section 7.1 of ODS.
    
• Lecture 20:
  • 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 21: Group testing
  • Single pooling and multiple pooling
    
• Lecture 22: 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 23: Planar graphs and crossing lemma (Last class!)
  • Planar graphs, Section 7.5.1
  • The crossing lemma, Section 7.5.2
    
• Final-exam review (no live class)
  • Solving the Winter 2019 Final Exam
    
  • Solving questions 19-25 on the Winter 2019 Final Exam