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

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

# 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

Day AM/PM Staff Time Location
Monday AM Kirk Zhen 8:30-10:30 4125 Herzberg
Monday PM Xiaoying Liu TBA 4125 Herzberg
Tuesday AM Pat Morin 9:00-11:00 5177 Herzberg
Tuesday PM Abdullah Alchihabi 2:40-4:40 4125 Herzberg
Wednesday AM Shelly Wang 10:00-12:00 4125 Herzberg
Wednesday PM Alexander Johns 2:40-4:40 4125 Herzberg
Thursday AM Alexa de Grandmont 9:00-11:00 4125 Herzberg
Thursday PM FX CC 1:30-3:30 4125 Herzberg
Friday AM Zoltan Kalnay 9:00-11:00 4125 Herzberg
Friday PM Mehrnoosh Javarsineh 13:00-15:00 4125 Herzberg

# Important Dates

Sunday Sep 22, 23:55 Assignment 1 due (in cuLearn)
Thursday Oct 17 Mid-term exam for Section A (in class)
Friday Oct 18 Mid-term exam for Section B (in class)

# Assignments

• Late assignments will not be accepted.
• 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.

Assignment 1 was due on Sunday September 22nd, before 23:55. Sample solutions for Assignment 1 are now available as a PDF file that was created from this LaTeX file.

Assignments will be posted here when they are available.

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:

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

• Sep 4/5: Introduction
• Course overview.
• Chapter 1 in the textbook: Ramsey Theory, Sperner's Theorem, Quick-Sort.
• Sep 6: Pigeonhole sampler
• Sep 10/11: Counting (1)
• Product Rule, Bijection Rule, Sections 3.1, 3.2.
• Sep 12/13: Counting (2)
• Complement Rule, Sum Rule, Inclusion-Exclusion, permutations, binomial coefficients, Sections 3.3, 3.4, 3.5, 3.6.
• Sep 17/18: Counting (3)
• Binomial coefficients, Newton's Binomial Theorem, combinatorial proofs, Vandermonde's Identity, Pascal's Triangle, Sections 3.6, 3.7.
• Sep 19/20: Counting (4)
• Sections 3.7 and 3.8.
• How many strings can be obtained from MISSISSIPPI, counting solutions of linear equations, Section 3.9.
• Sep 24/25: Pigeonhole Principle
• Exercises 3.84, 3.85, and 3.87, Section 3.10.1.
• Sep 26/27: Recursion (1)
• Recursive functions, Section 4.1.
• Fibonacci numbers, Section 4.2.
• Counting 00-free bitstrings, Section 4.2.1. Exercise 4.38.
• Oct 1/2: Recursion (2)
• Euclid's algorithm, Section 4.5.
• Oct 3/4: Recursion (3)
• MergeSort, Section 4.6.
• Oct 8/9: 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.
• Oct 10/11:
• Uniform probability spaces, Section 5.4.
• Exercise 5.11, which is known as the Newton Pepys problem.
• Oct 15/16:
• Midterm review and slack time
• Oct 17/18:
• Midterm exam

... to be continued ...