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.

Office hours: Wednesday and Friday, 4 - 5 pm.

All office hours will use Big Blue Button. On the main cuLearn page for this course, click "Office Hours" in Topic 2.
Office hours start on Monday September 14.

Teaching assistants:

Yuan Wu
- Office hours: Monday, 9-11 am
Zoltan Kalnay
- Office hours: Tuesday, 3-5 pm
Jason Dunn
- Office hours: Wednesday, 10-noon
Alexa De Grandmont
- Office hours: Monday, 1-3 pm
Joyce Bacic
- Office hours: Thursday, 3:30-5:30 pm
Yuelin Liu
- Office hours: Friday, 9-11 am

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

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

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.

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.

Midterm:

Information about the midterm will be posted here.

Final exam:

Information about the final exam will be posted here.

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.

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

January 23:
- 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.
January 25:
- Pigeonhole Principle, Exercises 3.84, 3.85, and 3.87, Section 3.10.1.
January 30:
- 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.
February 1:
- Recursion: Euclid's algorithm, Section 4.5.
February 6:
- Recursion: MergeSort, Section 4.6.
- Recursion: I am skipping this this term, because we are behind schedule; you should read this by yourself: Exercise 4.69, my notes are here.
February 8:
- 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.
February 13: Snow day. Class cancelled.
February 15:
- 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.
February 18-22: Winter break.
February 27: Midterm
March 1:
- Birthday paradox, Section 5.5.
- Find the big box, Section 5.6.
March 6:
- 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.
March 8:
- Independent events, Section 5.11.
- Exercise 5.81.
March 13:
- 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.
March 15:
- Infinite probability spaces, Section 5.15, Exercises 5.85 and 5.91.
March 20:
- Random variables, Section 6.1.
- Independent random variables, Section 6.2.
March 22:
- Expected value, Section 6.4.
- Linearity of expectation, Section 6.5.
- Geometric distribution and its expected value, Section 6.6, Exercise 6.35.
March 27:
- Binomial distribution and its expected value, Section 6.7.
- Indicator random variables, Section 6.8, Exercises 6.40 and 6.58 (same as winter 2017, A4, Q7).
March 29:
- Indicator random variables, finish Exercise 6.58.
- Largest elements in prefixes of random permutations, Section 6.8.2.
- Estimating the harmonic number, Section 6.8.3.
- I am skipping this this term, because we are behind schedule: Expected running time of Insertion-Sort, Section 6.9.
- Introduction to Quick-Sort, Section 6.10.
April 3:
- Expected running time of Quick-Sort, Section 6.10.
- Most likely, I will skip skip lists. Instead, I will teach group testing, detailed notes will be provided.
- Introduction to skip lists, Section 6.11.
April 5:
- Skip lists, Section 6.11.
April 10:
- Old exam: Fall 2018.

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

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