Fall 2015

- Ahmad Biniaz

Office hours: Thursday, 12:40pm-2:40pm. - Farah Chanchary

Office hours: Monday, 10am-noon. - Lei Chen

Office hours: Monday, 4:05pm-5:05pm. - Kimberly Crosbie

Office hours: Tuesday, 12:30pm-2:30pm. - Alina Shaikhet

Office hours: Thursday, 10am-noon. - 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 23 (in class)
- Final exam: Monday, December 21, 2-4pm, location TBA

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

- Late assignments will
**not**be accepted. - Assignment 1 is due October 1, before 4:30pm, in the course drop box in Herzberg 3115. Note that 3115 is open from 8:30am until 4:30pm.
- Assignment 2 is due October 15, before 4:30pm, in the course drop box in Herzberg 3115. Note that 3115 is open from 8:30am until 4:30pm.
- Assignment 3 is due November 19, before 4:30pm, in the course drop box in Herzberg 3115. Note that 3115 is open from 8:30am until 4:30pm.
- Assignment 4 is due December 3, before 4:30pm, in the course drop box in Herzberg 3115. Note that 3115 is open from 8:30am until 4:30pm.

- September 2:
- 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 4: No class, classes follow a Monday schedule.
- September 9:
- Counting: Product Rule, Section 3.1.

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

- September 16:
- Counting: binomial coefficients, Newton's Binomial Theorem, combinatorial proofs, Sections 3.6, 3.7.

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

- September 23:
- Pigeonhole Principle, Section 3.10.1.
- Recursion: recursive functions, Fibonacci numbers, Sections 4.1, 4.2.

- September 25:
- Recursion: Counting 00-free bitstrings, gossip problem, MergeSort, Sections 4.2.1, 4.4, 4.5.

- September 30:
- Recursion: MergeSort, cutting a circle into regions, Sections 4.5, 4.6.

- October 2:
- Recursion: cutting a circle into regions, Section 4.6.

- October 7:
- 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 9:
- uniform probability spaces, birthday paradox, Sections 5.4, 5.5.

- October 14:
- Find the big box, Section 5.6.
- Let's Make a Deal, the Monty Hall Problem, Section 5.7.
- Conditional probability, Section 5.8.

- October 16:
- Conditional probability, Section 5.8.
- Independent events, Section 5.10.

- October 21:
- Independent events, Sections 5.10, 5.11.
- Choosing a random element in a linked list, Section 5.12.

- October 23: Midterm
- Answers midterm: 1D, 2C, 3D, 4B, 5C, 6A, 7C, 8B, 9A, 10D, 11B, 12B, 13C, 14A, 15B, 16A, 17C
- 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.
- Calculators are allowed.
- 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
- here is yet another old midterm. Answers: 1C, 2B, 3B, 4A, 5C, 6B, 7D, 8B, 9A, 10D, 11D, 12C, 13B, 14D, 15B, 16A, 17B

- October 26-30: Fall break
- November 4:
- Exercise 5.35.
- Long runs in random bitstrings, Section 5.13.

- November 6:
- Infinite probability spaces, Section 5.14.

- November 11:
- Random variables, Section 6.1.
- Independent random variables, Section 6.2.
- Distribution functions, Section 6.3: Read this section on your own.

- November 13:
- Expected value, Section 6.4.
- Linearity of expectation, Section 6.5.
- Geometric distribution and its expected value, Section 6.6.
- Binomial distribution and its expected value, Section 6.7.

- November 18:
- Binomial distribution and its expected value, Section 6.7.
- Indicator random variables, Exercise 6.17 and Section 6.8.

- November 20:
- Where does Question 8 in Assignment 3 come from?
- Estimating the harmonic number, Section 6.8.3.
- Expected running time of Insertion-Sort, Section 6.9.

- November 25:
- Expected running time of Quick-Sort, Section 6.10.
- Skip lists, Section 6.11.

- November 27:
- Skip lists, Section 6.11.
- Probabilistic method: large bipartite subgraphs, Section 7.1.

- December 2:
- Ramsey Theory, Section 7.2.
- Sperner's Theorem, Section 7.3.

- December 4:
- Review.
- Solutions midterm. Please bring the midterm, so that I do not have to write all questions on the board.

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: