Discrete Structures II (COMP 2804)
Fall 2018

• Location TA's office hours: Herzberg Building 5336
• Tri Cao
  Office hours: Monday 3-5
  
• Alexa de Grandmont
  Office hours: Friday 10-noon
• Zoltan Kalnay
  Office hours: Tuesday 10-noon
• Yingjie Song
  Office hours: Monday 10:30-12:30
• Tyler Tuttle
  Office hours: Thursday 2-4
• 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 Thursday September 13, due Sunday September 30
• Assignment 2: posted Sunday September 30, due Sunday October 14
• Midterm: Friday October 19 (in class)
• Assignment 3: posted Thursday November 1, due Thursday November 15
• Assignment 4: posted Thursday November 15, due Thursday November 29
• 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 Sunday September 30, before 11:55pm.
  • The assignment has been updated: In Q5, the variables f, m, and k are all at least 2.
  • Here is Assignment 1 as a pdf file.
  • Here is the LaTeX file, here is the figure.
  • I used the freely available Ipe drawing editor to make the figure.
  • Here are the solutions.
• Assignment 2 is due Sunday October 14, before 11:55pm.
  • Here is Assignment 2 as a pdf file.
  • Here is the LaTeX file.
  • Here are the solutions.

• Here you find assignments from previous terms.
• Here you find midterms from previous terms.
• Exams from previous terms will be posted here.

• 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.
• Bring pencils (the scantron machine prefers pencils).

• Information about the final exam will be posted here.

• September 5:
  • 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 7:
  • Counting: Product Rule, Bijection Rule, Sections 3.1, 3.2.
• September 12:
  • Counting: Complement Rule, Sum Rule, Inclusion-Exclusion, permutations, binomial coefficients, Sections 3.3, 3.4, 3.5, 3.6.
• September 14:
  • Counting: binomial coefficients, Newton's Binomial Theorem, combinatorial proofs, Sections 3.6, 3.7.
• September 19:
  • Counting: Vandermonde's Identity, Pascal's Triangle, how many strings can be obtained from MISSISSIPPI, counting solutions of linear equations, Sections 3.8, 3.9.
  • Pigeonhole Principle, Section 3.10, Exercise 3.68.
• September 21:
  • Pigeonhole Principle, Exercises 3.69 and 3.71, Section 3.10.1.
  • Recursion: recursive functions, Section 4.1.
• September 26:
  • Recursion: Fibonacci numbers, Section 4.2.
  • Recursion: Counting 00-free bitstrings, Section 4.2.1.
  • Recursion: Euclid's algorithm, this is not in the textbook yet. My notes are here.
• September 28:
  • Recursion: Euclid's algorithm.
  • Recursion: MergeSort, Section 4.5.
• October 3:
  • Recursion: Running time of MergeSort, Section 4.5.
  • Recursion: Exercise 4.59, my notes are here.
• October 5:
  • 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 10:
  • Basic rules of probability, Section 5.3.
  • Uniform probability spaces, Section 5.4.
  • Exercise 5.10, which is known as the Newton Pepys problem.
• October 12:
  • Birthday paradox, Section 5.5.
  • Find the big box, Section 5.6.

• October 17:
  • Let's Make a Deal, the Monty Hall Problem, Section 5.7.
  • Anil's kids, definition of Conditional probability, up to Section 5.8.1.
  • Conditional probability, Section 5.8.
  • Independent events, Section 5.11.
• October 19: Midterm
• October 22-26: Fall break
• October 31:
  • Pairwise and mutually independent events, Section 5.11.3, Exercise 5.61, Section 5.12.
  • The probability of a circuit failing, Section 5.12.3.
• November 2:
  • Choosing a random element in a linked list, Section 5.13.
  • Long runs in random bitstrings, Section 5.14.
• November 7:
  • Infinite probability spaces, Section 5.15, Exercises 5.63 and 5.68.
• November 9:
  • Random variables, Section 6.1.
• November 14:
  • Independent random variables, Section 6.2.
  • Expected value, Section 6.4.
• November 16:
  • Linearity of expectation, Section 6.5.
  • Geometric distribution and its expected value, Section 6.6.
  • Exercise 6.24.
  • Binomial distribution and its expected value, Section 6.7.
• November 21:
  • Indicator random variables, Section 6.8, Exercises 6.29 and 6.46.
• November 23:
  • Indicator random variables, Section 6.8.2.
  • Estimating the harmonic number, Section 6.8.3.
  • Expected running time of Insertion-Sort, Section 6.9.
• November 28:
  • Expected running time of Quick-Sort, Section 6.10.
  • Skip lists, Section 6.11.
• November 30:
  • Analysis of skip lists, Section 6.11.3.
• December 5:
  • Solutions midterm and old exam.