Fall 2014

- TBA
- 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 17, due October 1
- Assignment 2: posted October 1, due October 15
- Assignment 3: posted November 5, due November 19
- Assignment 4: posted November 19, due December 3
- Midterm: Friday October 24 (in class)
- Final exam: TBA

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

- Late assignments will
**not**be accepted. - Assignments will be posted here.

- Will appear here

- September 5:
- Course overview. Some examples (without proofs): 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 10:
- Counting: Product Rule, Bijection Rule.

- September 12:
- Counting: Complement Rule, Sum Rule, Inclusion-Exclusion, Pigeonhole Principle.

- September 17:
- Counting: permutations, binomial coefficients, Newton's Binomial Theorem, combinatorial proofs.

- September 19:
- Counting: Combinatorial proofs.

- September 24:
- Recursion.

- September 26:
- Recursion.

- October 1:
- Recursion.

- October 3:
- Recursion.

- October 8:
- Dining Cryptographers, sample spaces and probability functions.

- October 10:
- Basic rules of probability, uniform probability spaces.

- October 15:
- Birthday paradox, find the big box.

- October 17:
- Let's Make a Deal, the Monty Hall Problem.
- Conditional probability, independent events.

- October 22:
- Independent events.

- October 24: Midterm
- October 27-31: Reading week
- November 5:
- Independent events.

- November 7:
- Infinite probability spaces.

- November 12:
- Random variables, independent random variables.

- November 14:
- Distribution functions, expected value, linearity of expectation.

- November 19:
- Geometric distribution and its expected value, binomial distribution and its expected value, indicator random variables.

- November 21:
- How many times does the maximum change? Expected running times of Insertion-Sort and Quick-Sort.

- November 26:
- Skip Lists.

- November 28:
- Skip lists, the probabilistic method (large bipartite subgraphs).

- December 3:
- The probabilistic method.

- December 5:
- Review.
- Solutions midterm.

The undergraduate advisor for the School of Computer Science is available in Room 5302C HP, by telephone at 520-2600, ext. 4364 or by email at undergraduate_advisor@scs.carleton.ca. The advisor can assist with information about prerequisites and preclusions, course substitutions/equivalencies, understanding your academic audit and the remaining requirements for graduation. The undergraduate advisor will also refer students to appropriate resources such as the Science Student Success Centre, Learning Support Services and the Writing Tutorial Services.

- 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.

You may need special arrangements to meet your academic obligations during the term. For an accommodation request the processes are as follows: