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.
- Assignment 3 is due Wednesday March 22, before 4:30pm, in the course drop box in Herzberg 3115.
- Assignment 4 is due Wednesday April 5, 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:
- Winter 2017
- Answers Winter 2017: 1C, 2B, 3D, 4BD, 5A, 6C, 7D, 8C, 9A, 10D, 11B, 12C, 13B, 14D, 15B, 16B, 17A.
- For Q4: For n at least 13, B is the correct answer. For n=12, B is not the correct answer; in this case both A and C are wrong as well; thus, the correct answer is D. Because of this confusion, either of the answers B and D will be considered correct.

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

- March 1: Midterm
- March 6:
- Conditional probability, Section 5.9.3.
- Independent events, Sections 5.12 and 5.13.

- March 8:
- Exercise 5.46.
- The probability of a circuit failing, Section 5.13.3.

- March 13:
- Choosing a random element in a linked list, Section 5.14.
- Long runs in random bitstrings, Section 5.15.

- March 15:
- Long runs in random bitstrings, Section 5.15.
- Infinite probability spaces, Section 5.16, Exercises 5.48 and 5.52.

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

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

- March 29:
- Indicator random variables, Section 6.8.2, Exercise 6.24.
- Estimating the harmonic number, Section 6.8.3.
- 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.