Fall 2016

- Yaser Alwattar

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

Office hours: Friday, 1-3pm

Extra office hours: Wednesday November 23, 10-noon.

No office hours on Friday December 2. - 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: Wednesday December 14, 7-9pm

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

- Final exam: Wednesday December 14, 7-9pm.
- Calculators are allowed.
- The exam will be multiple-choice, 25 questions. It covers everything we have done in class, assignments, and midterm. Below you find old exams.
- Fall 2013.
- Answers: 1C, 2C, 3B, 4B, 5A, 6A, 7D, 8C, 9A, 10A, 11D, 12B, 13A, 14C, 15D, 16A, 17B, 18B, 19C, 20D, 21A, 22A, 23B, 24B, 25C, 26A, 27C, 28A, 29A, 30D, 31B, 32B, 33D, 34A

- Winter 2014.
- Answers: 1B, 2C, 3D, 4B, 5D, 6A, 7C, 8A, 9A, 10B, 11D, 12C, 13C, 14D, 15A, 16C, 17C, 18B, 19B, 20D, 21B, 22A, 23C, 24D, 25C

- Fall 2014.
- Answers: 1B, 2C, 3D, 4B, 5A, 6B, 7A, 8B, 9C, 10D, 11B, 12A, 13B, 14C, 15A, 16B, 17B, 18A, 19A, 20B, 21D, 22C, 23C, 24A, 25C

- Winter 2015.
- Answers: 1C, 2A, 3B, 4B, 5B, 6D, 7D, 8B, 9C, 10A, 11A, 12D, 13B, 14C, 15D, 16A, 17B, 18A, 19B, 20B, 21B, 22C, 23D, 24A, 25C

- Fall 2015.
- Answers: 1C, 2A, 3C, 4B, 5B, 6D, 7A, 8C, 9B, 10D, 11A, 12C, 13A, 14D, 15B, 16B, 17A, 18A, 19C, 20C, 21B, 22B, 23A, 24A, 25C

- 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.
- Assignment 3 is due Wednesday November 23, before 4:30pm, in the course drop box in Herzberg 3115.
- Assignment 4 is due Wednesday December 7, 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.
- Here is an extended version of Section 5.8 in the textbook.

- November 2: Midterm
- Here is the fall 2016
midterm.

Answers: 1B, 2D, 3C, 4B, 5C, 6A, 7C, 8C, 9D, 10A, 11B, 12D, 13B, 14C, 15C, 16D, 17B - 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:
- Fall 2013. Answers: 1C, 2B, 3C, 4B, 5D, 6D, 7A, 8C, 9A, 10B, 11D, 12C, 13A, 14C, 15D, 16C, 17B
- Winter 2014. Answers: 1C, 2D, 3B, 4A, 5A, 6B, 7C, 8B, 9D, 10A, 11B, 12A, 13C, 14D, 15A, 16B, 17B
- Fall 2014. Answers: 1c, 2c, 3d, 4d, 5a, 6c, 7b, 8a, 9b, 10c, 11b, 12c, 13d, 14c, 15a, 16a, 17d
- Winter 2015. Answers: 1C, 2B, 3B, 4A, 5C, 6B, 7D, 8B, 9A, 10D, 11D, 12C, 13B, 14D, 15B, 16A, 17B
- Fall 2015. Answers midterm: 1D, 2C, 3D, 4B, 5C, 6A, 7C, 8B, 9A, 10D, 11B, 12B, 13C, 14A, 15B, 16A, 17C

- Here is the fall 2016
midterm.
- November 7:
- Law of Total Probability, Section 5.9.
- Please take a seat. This is not in the textbook yet. You can download it here.

- November 9:
- Independent events, Sections 5.10, 5.11.
- Exercise 5.39.

- November 14:
- 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.

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

- November 21:
- Independent random variables, Section 6.2.
- Expected value, Section 6.4.

- November 23:
- 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.

- November 28:
- 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.

- November 30:
- Expected running time of Insertion-Sort, Section 6.9.
- Expected running time of Quick-Sort, Section 6.10.

- December 5:
- Skip lists, Section 6.11.

- December 7:
- Skip lists, Section 6.11.
- Probabilistic method: large bipartite subgraphs, Section 7.1.

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