Discrete Structures II (COMP 2804)
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.
  • Here is Assignment 1 as a pdf file.
  • Here is the LaTeX file.

• 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, MergeSort, Sections 4.2.1, 4.4, 4.5.
• October 3:
  • Recursion: MergeSort, cutting a circle into regions, Sections 4.5, 4.6.
• October 5:
  • Recursion: cutting a circle into regions, Section 4.6.
• October 10:
  • Thanksgiving, no class.
• October 12:
  • Anonymous broadcasting: Dining Cryptographers, Section 5.1.
  • Probability Theory: Probability spaces, sample spaces, probability functions, Section 5.2.
  • Basic rules of probability, Section 5.3.
• October 17:
  • uniform probability spaces, birthday paradox, Sections 5.4, 5.5.
• October 19:
  • Find the big box, Section 5.6.
  • Let's Make a Deal, the Monty Hall Problem, Section 5.7.
  • Conditional probability, Section 5.8.
• October 24-28: Fall break
• October 31:
  • Conditional probability, Section 5.8.
  • Independent events, Section 5.10.
• November 2: Midterm
• 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.