Discrete Structures II (COMP 2804)
Winter 2019

• TA's office hours will be held in Herzberg Building 5336
• Alexa de Grandmont
  Office hours: Friday 9:30 - 11:30
• Justin Lo
  Office hours: Thursday 1:30 - 3:30
• Luke Connolly
  Office hours: Wednesday 10:30 - 12:30
• Mohamed Kazma
  Office hours: Monday 3-5
• Zoltan Kalnay
  Office hours: Thursday 10 - noon
• Yingjie Song
  Office hours: Tuesday 12:30 - 2:30
• Tyler Tuttle
  Office hours: Monday 1:30 - 3:30
• Vincent Wang
  Office hours: Tuesday 10:30 - 12:30
• Yuan Wu
  Office hours: Thursday 10 - noon

• The following free textbook will be used: 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 17, due January 31
• Assignment 2: posted January 31, due February 14
• Midterm: Wednesday February 27 (in class)
• Assignment 3: posted March 7, due March 21
• Assignment 4: posted March 21, due April 4
• 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.
• Each assignment must be submitted as one single PDF file through cuLearn.
• You can type your solutions, or write them by hand and scan them (for example, using a scan app on your phone or using a real scanner).
• Instructions on how to submit your assignment can be found here.

• Assignment 1 is due Thursday January 31, before 11:55pm.
  • Here is Assignment 1 as a pdf file.
  • Here is the LaTeX file.
  • Here are the solutions.
  • Here are the solutions as a LaTeX file, and here and here are the figures.
  • I used the freely available Ipe drawing editor to make the figures.
• Assignment 2 is due Thursday February 14, before 11:55pm.
  • Here is Assignment 2 as a pdf file.
  • Here is the LaTeX file.
  • Here are the solutions.
  • Here are the solutions as a LaTeX file, and here and here are the figures.

• Here you find assignments from previous terms.
• Here you find midterms from previous terms.
• Here you find final exams from previous terms.

• For the midterm, you have to know everything we did in class up to and including the February 15 lecture, as well as the first two assignments.
• Calculators are allowed.
• Bring pencils (the scantron machine prefers pencils).

• Final exam: TBA
• Calculators are allowed.
• Bring pencils (the scantron machine prefers pencils).
• The exam will be multiple-choice, 25 questions. It covers everything we have done in class, assignments, and midterm.

• 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, Bijection Rule, Sections 3.1, 3.2.
• January 16:
  • Counting: Complement Rule, Sum Rule, Inclusion-Exclusion, permutations, binomial coefficients, Sections 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, Sections 3.7 and 3.8.
  • Counting: How many strings can be obtained from MISSISSIPPI, counting solutions of linear equations, Section 3.9.
• January 25:
  • Pigeonhole Principle, Exercises 3.76, 3.77, and 3.79, Section 3.10.1.
• January 30:
  • Recursion: Recursive functions, Section 4.1.
  • Recursion: Fibonacci numbers, Section 4.2.
  • Recursion: Counting 00-free bitstrings, Section 4.2.1.
  • Recursion: Exercise 4.35.
• February 1:
  • Recursion: Euclid's algorithm, Section 4.5.
• February 6:
  • Recursion: MergeSort, Section 4.6.
  • Recursion: I am skipping this this term, because we are a bit behind schedule; you should read this by yourself: Exercise 4.63, my notes are here.
• February 8:
  • 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.
• February 13: Snow day. Class cancelled.
• February 15:
  • Uniform probability spaces, Section 5.4.
  • Exercise 5.11 (same as Q4 of A3 of Fall 2017), which is known as the Newton Pepys problem.

• February 18-22: Winter break.
• February 27: Midterm
• March 1:
  • Birthday paradox, Section 5.5.
  • Find the big box, Section 5.6.
• March 6:
  • Let's Make a Deal, the Monty Hall Problem, Section 5.7.
  • Conditional probability, Section 5.8.
  • Anil's kids, Exercise 5.37, same as Q3 of A3 of Winter 2018.
• March 8:
  • Independent events, Section 5.11.
  • Exercise 5.76.
• March 13:
  • Finish Exercise 5.76.
  • Section 5.12, in particular, the probability of a circuit failing, Section 5.12.3.
  • Choosing a random element in a linked list, Section 5.13.
• March 15:
  • Infinite probability spaces, Section 5.15, Exercises 5.78 and 5.83.
• March 20:
  • Random variables, Section 6.1.
  • Independent random variables, Section 6.2.
• March 22:
  • Expected value, Section 6.4.
  • Linearity of expectation, Section 6.5.
  • Geometric distribution and its expected value, Section 6.6, Exercise 6.34.
• March 27:
  • Binomial distribution and its expected value, Section 6.7.
  • Indicator random variables, Section 6.8, Exercises 6.39 and 6.57 (same as winter 2017, A4, Q7).
• March 29:
  • Indicator random variables, Exercise 6.41 (same as fall 2017, A4, Q6).
  • Indicator random variables, Section 6.8.2.
  • Estimating the harmonic number, Section 6.8.3.
• April 3:
  • Expected running time of Insertion-Sort, Section 6.9.
  • Expected running time of Quick-Sort, Section 6.10.
• April 5:
  • Skip lists, Section 6.11.
• April 10:
  • Analysis of skip lists, Section 6.11.3.
  • Solutions midterm and old exam.