Fall 2014

- Farah Chanchary, office hours: Thursday 8:30-10:30am
- Tommy Reddad, office hours: Wednesday 10-noon. Tommy does not have office hours on September 17.
- Peter Simonyi, office hours: Thursday noon-2pm
- 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. - Assignment 1 is due October 1, before 23:59pm, in the course drop box in Herzberg 3115.

- 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 10:
- Counting: Product Rule, Section 3.1.

- September 12:
- Counting: Bijection Rule, Complement Rule, Sum Rule, Inclusion-Exclusion, permutations, Sections 3.2, 3.3, 3.4, 3.5, 3.6.

- September 17:
- Counting: binomial coefficients, Newton's Binomial Theorem, Section 3.6.

- September 19:
- Counting: combinatorial proofs, Vandermonde's Identity, Pascal's Triangle, how many strings can be obtained from MISSISSIPPI, counting solutions of linear equations, Sections 3.7, 3.8, 3.9.

- September 24:
- Pigeonhole Principle, 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: