Winter 2017

- Yaser Alwattar

Office hours: Tuesday noon-2pm - Farah Chanchary

Office hours: Monday 1:30-3:30pm - Kimberly Crosbie

Office hours: Tuesday 1-3pm - Omar Ben Ismail

Office hours: Thursday 1:30-3:30pm - Sehwan Lee

Office hours: Wednesday 2-4pm - Rui Li

Office hours: Monday 5:30-7:30pm - Nicolas Perez

Office hours: Friday 11am-1pm - The TAs have their office hours in Herzberg Building 1170.

- 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
- Assignment 3: posted March 8, due March 22
- Assignment 4: posted March 22, due April 5
- Midterm: Wednesday March 1 (in class)
- 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.
- Assignment 1 is due Wednesday February 1, before 4:30pm, in the course drop box in Herzberg 3115.
- Assignment 2 is due Wednesday February 15, before 4:30pm, in the course drop box in Herzberg 3115.

- 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.
- To get an idea what to expect, here are old midterms:

- 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, Section 3.1.

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

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

- January 23:
- Counting: Vandermonde's Identity, Pascal's Triangle, how many strings can be obtained from MISSISSIPPI, counting solutions of linear equations, Sections 3.7, 3.8, 3.9.

- January 25:
- Counting solutions of linear equations and inequalities, Section 3.9.2, Exercise 3.45.
- Pigeonhole Principle, Section 3.10.1, Exercises 3.48, 3.50.
- Recursion: recursive functions, Section 4.1.

- January 30:
- Recursion: Fibonacci numbers, Section 4.2.
- Recursion: Counting 00-free bitstrings, gossip problem, Sections 4.2.1, 4.4.

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

- February 6:
- Recursion: cutting a circle into regions, Sections 4.6.1, 4.6.2, 4.6.3.

- February 8:
- Recursion: cutting a circle into regions, Section 4.6.
- Exercise 4.22.
- Anonymous broadcasting: Dining Cryptographers, Section 5.1.

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

- February 15:
- Uniform probability spaces, Section 5.4.
- Birthday paradox, Section 5.5.
- Find the big box, Section 5.6.

- February 20-24: Winter break
- February 27:
- Find the big box, Section 5.6.
- Let's Make a Deal, the Monty Hall Problem, Section 5.7.
- Conditional probability, Section 5.8.

- March 1: Midterm
- March 6:
- Law of Total Probability, Section 5.9.
- Please take a seat. This is not in the textbook yet.

- March 8:
- Independent events, Sections 5.10, 5.11.
- Exercise 5.39.

- March 13:
- The probability of a circuit failing, Section 5.11.3.
- Choosing a random element in a linked list, Section 5.12.
- Infinite series, Section 5.14.1.

- March 15:
- Infinite probability spaces, Section 5.14, Exercise 5.45.
- Random variables, Section 6.1.
- Independent random variables, Section 6.2.

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

- March 22:
- Linearity of expectation, Section 6.5.
- Geometric distribution and its expected value, Section 6.6.
- Binomial distribution and its expected value, Section 6.7.
- Indicator random variables, Exercise 6.19.

- March 27:
- Indicator random variables, Section 6.8, Exercise 6.31.
- Estimating the harmonic number, Section 6.8.3.
- Expected running time of Insertion-Sort, Section 6.9.

- March 29:
- Expected running time of Insertion-Sort, Section 6.9.
- Expected running time of Quick-Sort, Section 6.10.

- April 3:
- Skip lists, Section 6.11.
- Probabilistic method: large bipartite subgraphs, Section 7.1.

- April 5:
- Solutions midterm and previous exam.