Fall 2016

- Yaser Alwattar

Office hours: Tuesday, noon-2pm - Ahmad Biniaz

Office hours: Friday, 1-3pm - Farah Chanchary

Office hours: Thursday, 10-noon - Kimberly Crosbie

Office hours: Tuesday, 1-3pm - Sehwan Lee

Office hours: Wednesday, 10-noon - 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 September 21, due October 5
- Assignment 2: posted October 5, due October 19
- Assignment 3: posted November 9, due November 23
- Assignment 4: posted November 23, due December 7
- Midterm: Wednesday November 2 (in class)
- Final exam: TBA

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

- Late assignments will
**not**be accepted. - Assignment 1 is due Wednesday October 5, before 4:30pm, in the course drop box in Herzberg 3115.
- Assignment 2 is due Wednesday October 19, before 4:30pm, in the course drop box in Herzberg 3115.

- September 7:
- 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.

- September 12:
- Counting: Product Rule, Section 3.1.

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

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

- September 21:
- 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.

- September 26:
- Counting solutions of linear equations and inequalities, Section 3.9.2.
- Pigeonhole Principle, Section 3.10.1.
- Recursion: recursive functions, Section 4.1.

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

- October 3:
- Recursion: MergeSort, Section 4.5.

- October 5:
- Recursion: cutting a circle into regions, Sections 4.6.1, 4.6.2.

- October 10:
- Thanksgiving, no class.

- October 12:
- Recursion: cutting a circle into regions, Section 4.6.
- Anonymous broadcasting: Dining Cryptographers, Section 5.1.

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

- October 19:
- uniform probability spaces, birthday paradox, Sections 5.4, 5.5.
- Find the big box, Section 5.6.

- October 24-28: Fall break

- October 31:
- Find the big box, Section 5.6.
- Let's Make a Deal, the Monty Hall Problem, Section 5.7.
- Conditional probability, Section 5.8.
- Independent events, Section 5.10.

- November 2: Midterm
- For the midterm, you have to know everything we did in class up to and including the birthday problem, as well as the first two assignments.
- Calculators are allowed.
- To get an idea what to expect, below you find old midterms:

- November 7:
- Independent events, Sections 5.10, 5.11.
- Choosing a random element in a linked list, Section 5.12.

- November 9:
- Exercise 5.35.
- Long runs in random bitstrings, Section 5.13.

- November 14:
- Infinite probability spaces, Section 5.14.

- November 16:
- Random variables, Section 6.1.
- Independent random variables, Section 6.2.
- Distribution functions, Section 6.3: Read this section on your own.

- November 21:
- Expected value, Section 6.4.
- Linearity of expectation, Section 6.5.
- Geometric distribution and its expected value, Section 6.6.
- Binomial distribution and its expected value, Section 6.7.

- November 23:
- Binomial distribution and its expected value, Section 6.7.
- Indicator random variables, Exercise 6.17 and Section 6.8.

- November 28:
- Where does Question 8 in Assignment 3 come from?
- Estimating the harmonic number, Section 6.8.3.
- Expected running time of Insertion-Sort, Section 6.9.

- November 30:
- Expected running time of Quick-Sort, Section 6.10.
- Skip lists, Section 6.11.

- December 5:
- Skip lists, Section 6.11.

- December 7:
- Probabilistic method: large bipartite subgraphs, Section 7.1.
- Ramsey Theory, Section 7.2.
- Sperner's Theorem, Section 7.3.

- December 9:
- Review.
- Solutions midterm. Please bring the midterm, so that I do not have to write all questions on the board.