Winter 2018

- Location TA's office hours: Herzberg 4125
- Tri Cao

Office hours: Tuesday, 1-3 - Farah Chanchary

Office hours: Thursday, 2-4

- Francois-Xavier Chaplain Corriveau

Office hours: Friday, 9-11

- Gregory Corbould

Office hours: Wednesday, 4-6

- Alexa de Grandmont

Office hours: Monday, 1-3 - Omar Ben Ismail

Office hours: Tuesday, 2:30-4:30 - Nick Perez

Office hours: Thursday, 12:15-2:15

- Tyler Tuttle

Office hours: Wednesday, 2-4 - Shelly Wang

Office hours: Friday, 11:30-1:30

- The following free textbook will be used: Discrete Structures for Computer Science: Counting, Recursion, and Probability.
- Additional material: Discrete Mathematics and its Applications, by Rosen. This book contains a large number of exercises, as well as solutions. Do not buy this book, because it is too expensive. We used to use this book for COMP 1805, so you may still have an old copy, or you may borrow a copy from a friend.

- Assignment 1: posted January 18, due February 1
- Assignment 2: posted February 1, due February 15
- Midterm: Tuesday February 27 (in class)
- Assignment 3: posted March 8, due March 22
- Assignment 4: posted March 22, due April 5
- Final exam: TBA

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

- 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.
- 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) or take pictures using your phone.
- Instructions on how to submit your assignment can be found here.
- Assignment 1 is due Thursday February 1, before 11:55pm.
- Assignment 2 is due Thursday February 15, before 11:55pm.

- Counting:
- Recursion:
- Probability:

- For the midterm, you have to know everything we did in class up to and including the birthday paradox, as well as the first two assignments.
- Calculators are allowed.
- Bring pencils (the scantron machine prefers pencils).
- To get an idea what to expect, here are old midterms:

- Information about the final exam will be posted here.

- January 9:
- Course overview. Chapter 1 in the textbook: Ramsey Theory, Sperner's Theorem, Quick-Sort.
- 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 of the textbook and do some of the exercises at the end of that chapter.

- January 11:
- Counting: Product Rule, Bijection Rule, Sections 3.1, 3.2.

- January 16:
- Counting: Complement Rule, Sum Rule, Inclusion-Exclusion, permutations, binomial coefficients, Sections 3.3, 3.4, 3.5, 3.6.

- January 18:
- Counting: binomial coefficients, Newton's Binomial Theorem, combinatorial proofs, Vandermonde's Identity, Sections 3.6, 3.7.

- January 23:
- Counting: Pascal's Triangle, how many strings can be obtained from MISSISSIPPIMILLS, counting solutions of linear equations, Sections 3.8, 3.9.
- Pigeonhole Principle, Section 3.10, Exercises 3.61, 3.62, 3.65.

- January 25:
- Pigeonhole Principle, Section 3.10.1.
- Recursion: recursive functions, Fibonacci numbers, Sections 4.1, 4.2.

- January 30:
- Recursion: Counting 00-free bitstrings, gossip problem, Sections 4.2.1, 4.4.
- Recursion: Introduction to MergeSort, Section 4.5.

- February 1:
- Recursion: MergeSort, Section 4.5.

- February 6:
- Recursion: Exercise 4.52.
- Anonymous broadcasting: Dining Cryptographers, Section 5.1.

- February 8:
- Probability Theory: Probability spaces, sample spaces, probability functions, Section 5.2.
- Basic rules of probability, Section 5.3.
- Uniform probability spaces, Section 5.4.

- February 13:
- More on uniform probability spaces, Exercise 5.10, which is known as the Newton Pepys problem.
- Birthday paradox, Section 5.5.

- February 15:
- Find the big box, Section 5.6.
- Let's Make a Deal, the Monty Hall Problem, Section 5.7.
- Anil's kids, definition of Conditional probability, up to Section 5.8.1.

- February 19-23: Winter break
- February 27: Midterm
- March 1:
- Conditional probability, Section 5.8.

- March 6:
- Independent events, Section 5.11, Exercise 5.54, Section 5.12.1.

- March 8:
- The probability of a circuit failing, Section 5.12.3.
- Choosing a random element in a linked list, Section 5.13.
- Long runs in random bitstrings, Section 5.14.

- March 13:
- Long runs in random bitstrings, Section 5.14.
- Infinite probability spaces, infinite series, Sections 5.15 and 5.15.1, Exercise 5.56.

- March 15:
- Infinite probability spaces, Sections 5.15.2 and 5.15.3, Exercise 5.61.
- Random variables, Section 6.1.

- March 20:
- Random variables, Section 6.1.
- Independent random variables, Section 6.2.
- Expected value, Section 6.4.

- March 22:
- Expected value, Section 6.4.
- Linearity of expectation, Section 6.5.
- Geometric distribution and its expected value, Section 6.6.
- Exercise 6.21.
- Binomial distribution and its expected value, Section 6.7.

- March 27:
- Binomial distribution and its expected value, Section 6.7.
- Indicator random variables, Section 6.8, Exercises 6.26 and 6.42.

- March 29:
- Indicator random variables, Section 6.8.2.
- Estimating the harmonic number, Section 6.8.3.
- Expected running time of Quick-Sort, Section 6.10.

- April 3:
- Finish Quicksort, Section 6.10.
- Skip lists, Section 6.11.

- April 5:
- Skip lists, Section 6.11.

- April 10:
- Solutions midterm and an old exam.