Discrete Structures II (COMP 2804, Section B)
Fall 2020

Instructor: Michiel Smid
Office: Herzberg Building 5125C (Note that it is unlikely that we are allowed to enter Herzberg.)
E-mail: michiel@scs.carleton.ca

Lectures:

Official meeting times: Wednesday and Friday, 4:05 - 5:25 pm.
There won't be live lectures. Instead, links to pre-recorded video lectures will be posted in the section "What was done in class".

Fall term:

First lecture is on Wednesday September 9.
October 26-30: Fall break, no classes.
Last lecture is on Wednesday December 9.
Friday December 11: Last day of classes in the fall term. Classes follow a Monday schedule.

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.

Topics covered include: Counting, recursion, discrete probability, random variables, randomized algorithms. Material is illustrated through examples from computing.

Textbook:

The following free textbook will be used: Discrete Structures for Computer Science: Counting, Recursion, and Probability.
Additional material:
- Mathematics for Computer Science by Eric Lehman, F. Thomson Leighton, and Albert R. Meyer.

Important dates:

Assignment 1: due Sunday September 27 at 23:55
Assignment 2: due Sunday October 11 at 23:55
Midterm: Wednesday October 21, 16:00 - 17:30
Assignment 3: due Sunday November 22 at 23:55
Assignment 4: due Sunday December 6 at 23:55
Final exam: Friday December 18, 9:00 - 11:00

Grading scheme:

Assignments: 25%
Midterm: 25%
Final exam: 50%

Assignments:

Late assignments will not be accepted.
Real computer scientists use LaTeX to type their solutions. In case you want to learn LaTeX, here is a tutorial.
You can use the freely available Ipe drawing editor to make figures.
Each assignment must be submitted as one single PDF file through cuLearn.
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).

Assignment 1 is due Sunday September 27, before 11:55 pm.
- Here is Assignment 1 as a pdf file.
- Here is the LaTeX file.
- Here are the solutions.
Assignment 2 is due Sunday October 11, before 11:55 pm.
- Here is Assignment 2 as a pdf file.
- Here is the LaTeX file.
- Here are the solutions.
Assignment 3 is due Sunday November 22, before 11:55 pm.
- Here is Assignment 3 as a pdf file.
- Here is the LaTeX file and here is the photo.
- Here are the solutions.
Assignment 4 is due Sunday December 6, before 11:55 pm.
- Here is Assignment 4 as a pdf file.
- Here is the LaTeX file.
- Here are the solutions.

Practice problems and old midterms/exams:

Here you find assignments from previous terms.
Here you find midterms from previous terms.
Here you find final exams from previous terms.

Your TA Alexa de Grandmont, together with Matthew MacRae-Bovell and Forest Anderson, have developed the Computer Science Study Center. You will find interactive on-line versions of previous midterms for this course. More material will be added.

Midterm:

The midterm will be on Wednesday October 21, 16:00 - 17:30.
Sign in to cuLearn on Wednesday October 21 by 16:00 and click the midterm exam link to begin.
You have to know everything that was done in the lectures up to, and including, October 14, as well as the first two assignments.

Final exam:

The final exam will be on Friday December 18, 9:00 - 11:00 am.
Note that Carleton's Final Exam Schedule says that the exam will be three hours. This is an error. The exam will be two hours.
The format will be the same as for the midterm.
Sign in to cuLearn on Friday December 18 by 9 am and click the final exam link to begin.
You have to know everything that was done in the lectures, as well as all four assignments.

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, first-year students (less than 4.0 credits completed): No credit for assessment(s) in question, or a final grade reduction of one full letter grade (e.g., A- becomes B-), whichever is a greater reduction.
First offence (anyone else): A grade of F in the course.
Second offence (anyone): A grade of F in the course and a one-term suspension from studies.
Third offence: Expulsion from the University.

Note: While these are the standard penalties, more severe penalties may be applied when warranted. For more information, click here.

What was done in class (chapter and section numbers refer to the textbook):

Video lecture 0: Very short intro to the course.
- You are supposed to 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 and do some of the exercises at the end of that chapter.
September 9:
- Video lecture 1, part 1.
- Video lecture 1, part 2.
- Chapter 1: Ramsey Theory, Sperner's Theorem, Quick-Sort.
September 11:
- Video lecture 2, part 1.
- Video lecture 2, part 2.
- Counting: Product Rule, Bijection Rule, Sections 3.1, 3.2.
September 16:
- Video lecture 3.
- Counting: Complement Rule, Sum Rule, Inclusion-Exclusion, permutations, introduction to binomial coefficients, Sections 3.3, 3.4, 3.5, 3.6.
September 18:
- Video lecture 4.
- Counting: binomial coefficients, Newton's Binomial Theorem, combinatorial proofs, Sections 3.6, 3.7.
September 23:
- Video lecture 5.
- Counting: Vandermonde's Identity, Pascal's Triangle, Sections 3.7 and 3.8.
- Counting: How many strings can be obtained from MISSISSIPPI, counting solutions of linear equations, Section 3.9.
September 25:
- Video lecture 6.
- Pigeonhole Principle, Exercises 3.84 and 3.85, Sections 3.10.1 and 3.10.2.
September 30:
- Video lecture 7.
- Recursion: Recursive functions, Section 4.1.
- Recursion: Fibonacci numbers, Section 4.2.
- Recursion: Counting 00-free bitstrings, Section 4.2.1.
- Recursion: Exercise 4.38.
October 2:
- Video lecture 8.
- Recursion: Euclid's algorithm, Section 4.5.
October 7:
- Video lecture 9.
- Recursion: MergeSort, Section 4.6.
- Recursion: Exercise 4.69, read this by yourself, my notes are here.
October 9:
- Video lecture 10.
- 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.
October 14:
- Video lecture 11.
- Uniform probability spaces, Section 5.4.
- Exercise 5.11 (same as Q4 of A3 of Fall 2017), which is known as the Newton Pepys problem.
October 16:
- Video lecture 12, part 0. This short video goes over Sections 5.2 and 5.3 again. The purpose is to test my new set-up.
- Video lecture 12, part 1.
- Video lecture 12, part 2.
- Birthday paradox, Section 5.5.
- Find the big box, Section 5.6.
October 21: Midterm
October 23:
- Video lecture 13, part 1.
- Video lecture 13, part 2.
- Let's Make a Deal, the Monty Hall Problem, Section 5.7.
- Conditional probability, Section 5.8.
- Anil's kids, Exercise 5.40, same as Q3 of A3 of Winter 2018.
October 26-30: Fall break.
November 4:
- Video lecture 14, part 1.
- Video lecture 14, part 2.
- Independent events, Section 5.11.
- Exercise 5.81.
November 6:
- Video lecture 15, part 1.
- Video lecture 15, part 2.
- Section 5.12, in particular, the probability of a circuit failing, Section 5.12.3.
- Choosing a random element in a linked list, Section 5.13.
November 11:
- Video lecture 16, part 1.
- Video lecture 16, part 2.
- Infinite probability spaces, Section 5.15, Exercises 5.85 and 5.91.
November 13:
- Video lecture 17.
- Random variables, Section 6.1.
- Independent random variables, Section 6.2.
November 18:
- Video lecture 18, part 1.
- Video lecture 18, part 2.
- Expected value, Section 6.4.
- Linearity of expectation, Section 6.5.
- Geometric distribution and its expected value, Section 6.6, Exercise 6.35.
November 20:
- Video lecture 19, part 1.
- Video lecture 19, part 2.
- Binomial distribution and its expected value, Section 6.7.
- Indicator random variables, Section 6.8, Exercise 6.40.
November 25:
- Video lecture 20, part 1.
- Video lecture 20, part 2.
- Indicator random variables, Exercise 6.58 (same as winter 2017, A4, Q7).
- Largest elements in prefixes of random permutations, Section 6.8.2.
- Estimating the harmonic number, Section 6.8.3.
November 27:
- Video lecture 21, part 1.
- Video lecture 21, part 2.
- Expected running time of Insertion-Sort, Section 6.9.
- Expected running time of Quick-Sort, Section 6.10.
December 2:
- Video lecture 22, part 1.
- Video lecture 22, part 2.
- Group testing.
- This is not in the textbook. My notes are here.
- Dorfman's paper from 1943 is here.
December 4:
- Video lecture 23.
- The probabilistic method:
  - Large bipartite subgraphs, Section 7.1.
  - Sperner's Theorem, Section 7.3.
December 9:
- Video lecture 24.
- Planar graphs and Euler's formula, Section 7.5.1.
- The crossing lemma, Section 7.5.2.

Tentative schedule (based on the last time I taught this course)

Friday December 11:
- No lecture: Classes follow a Monday schedule.

Discrete Structures II (COMP 2804, Section B) Fall 2020

Discrete Structures II (COMP 2804, Section B)
Fall 2020