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 Friday November 30
• Final exam: Tuesday December 18, 2-4pm, Alumni Hall, rows 26-39

• 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.
• Assignment 3 is due Thursday November 15, before 11:55pm.
  • Here is Assignment 3 as a pdf file.
  • Here is the LaTeX file.
  • Here are the solutions.
• Assignment 4 is due Friday November 30, before 11:55pm.
  
  • Here is Assignment 4 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.
• 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 birthday paradox, as well as the first two assignments.
• Calculators are allowed.
• Bring pencils (the scantron machine prefers pencils).

• Final exam: Tuesday December 18, 2-4pm, Alumni Hall, rows 26-39
• 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.

• 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.
  • Conditional probability, Section 5.8.
  • Anil's kids, Exercise 5.33, same as Q3 of A3 of Winter 2018.
• October 19: Midterm
• October 22-26: Fall break
• October 31:
  • Independent events, Section 5.11.
  • Exercise 5.69.
• November 2:
  • Finish Exercise 5.69.
  • 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.
• November 7:
  • Infinite probability spaces, Section 5.15, Exercises 5.71 and 5.76.
• November 9:
  • Random variables, Section 6.1.
  • Independent random variables, Section 6.2.
• November 14:
  • Expected value, Section 6.4.
  • Linearity of expectation, Section 6.5.
  • Geometric distribution and its expected value, Section 6.6, Exercise 6.29.
• November 16:
  • Binomial distribution and its expected value, Section 6.7.
  • Indicator random variables, Section 6.8, Exercises 6.34 and 6.51 (same as winter 2017, A4, Q7).
• November 21:
  • Indicator random variables, Exercise 6.36 (same as fall 2017, A4, Q6).
  • Indicator random variables, Section 6.8.2.
  • Estimating the harmonic number, Section 6.8.3.
• November 23:
  • Expected running time of Insertion-Sort, Section 6.9.
  • Expected running time of Quick-Sort, Section 6.10.
• November 28:
  • Skip lists, Section 6.11.
• November 30:
  • Analysis of skip lists, Section 6.11.3.
• December 5:
  • Solutions midterm and old exam.

• We are done!