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

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

Learning Modality

In Fall 2020, content for this course will be delivered online. Initially, at least, the plan is to do it as a YouTube Live Stream. I will give lectures from a classroom in my basement that students can tune into at the scheduled time (see the lecture schedule below). Students can ask questions using YouTube's chat feature. In addition to being available as a live stream, high-quality recordings of these lectures will be made available on YouTube, usually within 24 hours.

If anything goes wrong with the broadcast, I will not spend any significant amount of time trying to fix it. Instead, I will complete the lecture and post it online.

Here is the link for the first class live stream.

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.

Lecture and 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. These will be posted here when they become available.

Day		Staff	Time	Location
Mon	AM	Pat Morin	10:00-11:30	Lecture
Wed	AM	Pat Morin	10:00-11:30	Lecture

Important Dates


Sunday	Sep 27	23:55	Assignment 1 due (in cuLearn)
Sunday	Oct 11	23:55	Assignment 2 due (in cuLearn)
	Oct 24–28		Mid-term evaluation/exam
Sunday	Nov 15	23:55	Assignment 3 due (in cuLearn)
Tuesday	Dec 6	23:55	Assignment 4 due (in cuLearn)

Assignments

Assignments will be posted here as they become available.

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

Exams

The midterm and final exams will take place online. At the scheduled exam time, the exam will proceed as follows:

You will login to Zoom with your camera turned and using your full real name.
The Zoom session will have instructions on how to access the online exam
If you have a question during the exam, you can "raise your hand" (a Zoom feature) and an exam proctor will contact you through Zoom chat.
At some point during the exam, a proctor will check your student id (sign in).
When you have completed and submitted your online exam, you will "raise your hand" and an exam proctor will contact you through Zoom chat to give you permission to leave (sign out).

Any online exams completed by a student who did not properly sign in and sign out will be discarded.

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

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.

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


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

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.

Sep 9: Introduction
- Course overview.
- Chapter 1 in the textbook: Ramsey Theory, ~~Sperner's Theorem,~~ Quick-Sort.
Jan 9: Counting (1)
- Product Rule, Sections 3.1
Jan 14: Counting (2)
- Bijection Rule, Complement Rule, Sum Rule, The Principle of Inclusion-Exclusion, Sections 3.2, 3.3, 3.4, 3.5.
Jan 16: Counting (3)
- Binomial coefficients, Newton's Binomial Theorem, combinatorial proofs, Vandermonde's Identity, Pascal's Triangle, Sections 3.6, 3.7.
Jan 21: 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
Jan 23: 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
- Infinity of primes, Section 3.10.4
Jan 28: 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\}$
Jan 30: Recursion (2)
- Exercise 4.38
- Euclid's algorithm, Section 4.5. (gcd.py)
Feb 4: Recursion (3) (Guest lecturer)
- MergeSort, Section 4.6.
Feb 6: Randomization and probability (Guest lecturer)
- 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.
Feb 11:
- Midterm review
Feb 13:
- Midterm exam
Feb 25:
- The Birthday Paradox (section 5.5)
- Find the big box (section 5.6)
Feb 27:
- Let's Make a Deal, the Monty Hall Problem, Section 5.7.
- Conditional probability, Section 5.8.
- Anil's kids, Exercise 5.40, the remarkable set B.
Mar 3:
- Independent events, Section 5.11.
- Exercise 5.81.
Mar 5:
- 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.
Mar 10:
- Infinite probability spaces, Section 5.15, Exercises 5.85 and 5.91.
- The law of total probability
Mar 12:
- Random variables, Section 6.1.
- Independent random variables, Section 6.2.
- Expected value, Section 6.4.
- Linearity of expectation, Section 6.5.

Mar 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.
Mar 19: (—)
- Estimating the harmonic number, Section 6.8.3.
- Expected running time of Quick-Sort, Section 6.10.
Mar 24:
- 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.
Mar 26: Skiplists
- Skiplists, Section 6.11
Mar 31: 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
Apr 2: Planar graphs and crossing lemma
- Planar graphs, Section 7.5.1
- The crossing lemma, Section 7.5.2
Apr 7: Exam review (Guest lecturer)
- Solving the Winter 2019 Final Exam
- Solving questions 19-25 on the Winter 2019 Final Exam