**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, morin@scs.carleton.ca

# 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

Assignments will be posted here as they become available.

- The Assignment 4 deadline has passed. Here are sample solutions.
- The Assignment 3 deadline has passed. Here are sample solutions.
- The Assignment 2 deadline has passed. Here are sample solutions. .
- The Assignment 1 deadline has passed. Here are sample solutions.

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

# Exams

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.

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

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

- Sep 9: Introduction
- Course overview.
- Chapter 1 in the textbook: Ramsey Theory, Quick-Sort, Sperner's Theorem.

- Sep 14: Counting (1)
- Product Rule, Section 3.1

- Product Rule, Section 3.1
- Sep 16: Counting (2)
- Bijection Rule, Complement Rule, Sum Rule, The Principle of Inclusion-Exclusion, Sections 3.2, 3.3, 3.4, 3.5.

- Bijection Rule, Complement Rule, Sum Rule, The Principle of Inclusion-Exclusion, Sections 3.2, 3.3, 3.4, 3.5.
- Sep 21: Counting (3)
- Binomial coefficients, Newton's Binomial Theorem, combinatorial proofs, Vandermonde's Identity, Pascal's Triangle, Sections 3.6, 3.7.

- Binomial coefficients, Newton's Binomial Theorem, combinatorial proofs, Vandermonde's Identity, Pascal's Triangle, Sections 3.6, 3.7.
- Sep 23: 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

- Sep 28: 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~~

- Sep 30: 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\}$

- Oct 5: Recursion (2)
- Exercise 4.38
- Euclid's algorithm, Section 4.5. (gcd.py)

- Oct 7: Recursion (3)
- MergeSort, Section 4.6.

- MergeSort, Section 4.6.
- Oct 14: 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.

- Watch on your own:
- Midterm review using the Fall 2015 Midterm

- Midterm review using the Fall 2015 Midterm
- Oct 19: Two surprising examples
- The Birthday Paradox (section 5.5)
- Find the big box (section 5.6)

- Oct 21: Midterm exam on cuLearn
- Nov 2:
- 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.

- Nov 4:
- Independent events, Section 5.11.
- Exercise 5.81: Annie, Boris, and Charlie write an exam.

- Nov 9:
- 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.

- Nov 11:
- Infinite probability spaces, Section 5.15, Exercises 5.85 and 5.91.
- The law of total probability

- Nov 16:
- Random variables, Section 6.1.
- Independent random variables, Section 6.2.
- Expected value, Section 6.4.
- Linearity of expectation, Section 6.5.

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

- Nov 23: (—)
- Quick-Sort and random binary search trees, Section 6.10 and Section 7.1 of ODS.

- Quick-Sort and random binary search trees, Section 6.10 and Section 7.1 of ODS.
- Nov 25:
- 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.

- Nov 30: Group testing
- Dec 2: 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

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

- Solving the Winter 2019 Final Exam