Discrete Structures II (COMP 2804)
Winter 2015

• Farah Chanchary
  farahchanchary (@) cmail.carleton.ca
  office hours: Thursday 9-11.
• Lei Chen
  LeiChen3 (@) cmail.carleton.ca
  office hours: Monday 10:15-11:15.
• Alina Shaikhet
  AlinaShaikhet (@) cmail.carleton.ca
  office hours: Wednesday 10-noon.
• Ruba Skaik
  RubaSkaik (@) cmail.carleton.ca
  office hours: Tuesday and Thursday, 10:15-11:15.
• Andrew Trenholm
  AndrewTrenholm (@) cmail.carleton.ca
  office hours: Monday, noon-1pm.
• 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 January 15, due January 30
• Assignment 2: posted January 29, due February 13
• Assignment 3: posted March 10, due March 25
• Assignment 4: posted March 24, due April 8
• Midterm: February 24 (in class)
• Final exam: TBA

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

• Late assignments will not be accepted.
• Assignment 1 is due January 30, before 9:00am, in the course drop box in Herzberg 3115. Note that 3115 is open from 8:30am until 4:30pm.
  • Here is Assignment 1 as a pdf file.
  • Here is the LaTeX file.
  • Here are the solutions.
  • The marks will be posted on cuLearn; they are out of 50. Breakdown of the marks: Q2: 3+3=6, Q3: 7, Q4: 7, Q5: 4+4=8, Q6: 3, Q7: 1+3+3=7, Q8: 6, Q9: 6
• Assignment 2 is due February 13, before 9:00am, in the course drop box in Herzberg 3115. Note that 3115 is open from 8:30am until 4:30pm.
  • Here is Assignment 2 as a pdf file.
  • Here is the LaTeX file.
  • Here, here, and here are the figures. I used Ipe to make these figures.
  • If you are new to LaTeX, here is a link to the Assignment LaTeX Template, made by Simon Pratt and Christian Delahousse. You can use the file assignment.tex to typeset your assignments.
  • The marks will be posted on cuLearn; they are out of 50. Breakdown of the marks: Q2: 6, Q3: 4, Q4: 4, Q5: 7, Q6: 7, Q7: 8, Q8: 6, Q9: 8
  • Here are the solutions.

• January 6:
  • 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 8:
  • Counting: Product Rule, Bijection Rule, Sections 3.1., 3.2.
• January 13:
  • Counting: Complement Rule, Sum Rule, Inclusion-Exclusion, permutations, binomial coefficients, Sections 3.3, 3.4, 3.5, 3.6.
• January 15:
  • Counting: binomial coefficients, Newton's Binomial Theorem, combinatorial proofs, Vandermonde's Identity, Pascal's Triangle, Sections 3.6, 3.7, 3.8.
• January 20:
  • Counting: How many strings can be obtained from MISSISSIPPI, counting solutions of linear equations and inequalities, Pigeonhole Principle, Sections 3.9, 3.10.1.
• January 22:
  • Recursion: recursive functions, Fibonacci numbers, Sections 4.1, 4.2.
• January 27:
  • Recursion: a recursively defined set, gossip problem, MergeSort, Sections 4.3, 4.4, 4.5.
• January 29:
  • Recursion: MergeSort, cutting a circle into regions, Sections 4.5, 4.6.
• February 3:
  • Recursion: cutting a circle into regions, Section 4.6.
• February 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.
• February 10:
  • uniform probability spaces, birthday paradox, Sections 5.4, 5.5.
• February 12:
  • Find the big box, Section 5.6.
  • Let's Make a Deal, the Monty Hall Problem, Section 5.7.
  • Conditional probability, Section 5.8.
• February 16-20: Reading week.
• February 24: Midterm
  • Answers midterm: 1C, 2B, 3B, 4A, 5C, 6B, 7D, 8B, 9A, 10D, 11D, 12C, 13B, 14D, 15B, 16A, 17B
  • For the midterm, you have to know everything we did in class up to and including the Monty Hall Problem, as well as the first two assignments.
  • To get an idea what to expect,
    • here is an old midterm. Answers: 1C, 2B, 3C, 4B, 5D, 6D, 7A, 8C, 9A, 10B, 11D, 12C, 13A, 14C, 15D, 16C, 17B
    • here is another old midterm. Answers: 1C, 2D, 3B, 4A, 5A, 6B, 7C, 8B, 9D, 10A, 11B, 12A, 13C, 14D, 15A, 16B, 17B
    • here is yet another old midterm. Answers: 1c, 2c, 3d, 4d, 5a, 6c, 7b, 8a, 9b, 10c, 11b, 12c, 13d, 14c, 15a, 16a, 17d
• February 26:
  • Conditional probability, Section 5.8.
  • Independent events, Section 5.10.

• March 3:
  • Independent events, Sections 5.10, 5.11.
• March 5:
  • Choosing a random element in a linked list, Section 5.12.
• March 10:
  • Long runs in random bitstrings, Section 5.13.
• March 12:
  • Infinite probability spaces, Section 5.14.
• March 17:
  • Random variables, Section 6.1.
  • Independent random variables, Section 6.2.
  • Distribution functions, Section 6.3.
• March 19:
  • Expected value, Section 6.4.
  • Linearity of expectation, Section 6.5.
  • Geometric distribution and its expected value, Section 6.6.
• March 24:
  • Binomial distribution and its expected value, Section 6.7.
  • Indicator random variables, Section 6.8.
• March 26:
  • Estimating the harmonic number, Section 6.8.3.
  • Expected running time of Insertion-Sort, Section 6.9.
  • Expected running time of Quick-Sort, Section 6.10.
• March 31:
  • Finish Quick-Sort, Section 6.10.
  • Skip lists, Section 6.11.
• April 2:
  • Skip lists, Section 6.11.
• April 7:
  • Review.
  • Solutions midterm.

• Students are encouraged to collaborate on assignments, but at the level of discussion only. When writing down the solutions, they must do so in their own words.
• Past experience has shown conclusively that those who do not put adequate effort into the assignments do not learn the material and have a probability near 1 of doing poorly on the exams.