- The final exam will be on Friday, April 25, 7-9pm.
- The exam will be multiple-choice, 25 questions.
- Here is the exam from last fall. This exam has more questions, because it was a 3-hour exam. The answers to this exam are: 1:C, 2:C, 3:B, 4:B, 5:A, 6:A, 7:D, 8:C, 9:A, 10:A, 11:D, 12:B, 13:A, 14:C, 15:D, 16:A, 17:B, 18:B, 19:C, 20:D, 21:A, 22:A, 23:B, 24:B, 25:C, 26:A, 27:C, 28:A, 29:A, 30:D, 31:B, 32:B, 33:D, 34:A

Winter Semester 2014

- Alexis Beingessner
- Office hours: Wednesday, 1-2pm

- Farah Chanchary
- Office hours: Friday, 9-11

- Darryl Hill
- Office hours: Thursday, 10-noon

- Andrew Schoenrock
- The TAs have their office hours in Herzberg Building 1170

- My detailed notes (with some exercises) will be posted after each lecture.
- Additional material:
- Mathematics for Computer Science. A free textbook by Eric Lehman, F. Thomson Leighton, and Albert R. Meyer.
- 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 may borrow a copy from a friend.

- Assignment 1: posted January 16, due January 30
- Assignment 2: posted January 30, due February 13
- Assignment 3: posted March 6, due March 20
- Assignment 4: posted March 20, due April 3
- Midterm: Thursday February 27 (in class)
- Final exam: Friday April 25, 7-9pm, Field House

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

- Late assignments will
**not**be accepted. - Assignment 1 is due January 30, before 23:59pm, in the course drop box in Herzberg 3115.
- Assignment 2 is due February 13, before 23:59pm, in the course drop box in Herzberg 3115.
- Here is the link to Simon's LaTeX template that was mentioned in class. If you use LaTeX for Assignments 3 and 4, then you will get one bonus mark (per assignment).
- Assignment 3 is due March 20, before 23:59pm, in the course drop
box in Herzberg 3115.
- Here is Assignment 3 as a pdf file.
- Here is the LaTeX file.
- The marks will be posted on cuLearn; they are out of 50. Breakdown of the marks: Q2: 4, Q3: 2+2+2=6, Q4: 4, Q5: 4, Q6: 3+3=6, Q7: 2+3+3=8, Q8: 1+1+1+1+1=5, Q9: 2+2+2+2=8, Q10: 5, use latex: 1 bonus mark
- Here are the solutions for Assignment 3.

- Assignment 4 is due April 3, before 23:59pm, in the course drop box in Herzberg 3115.

- January 7:
- 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 in the notes and do some of the exercises at the end of that chapter.

- January 9:
- Counting: Product Rule, Bijection Rule.
- Some practice problems from the Lehman-Leighton-Meyer textbook: 14.2, 14.3, 14.4, 14.16.

- January 14:
- Counting: Complement Rule, Sum Rule, Inclusion-Exclusion, Pigeonhole Principle.
- Some practice problems from the Lehman-Leighton-Meyer textbook: 14.33, 14.34, 14.38.

- January 16:
- Counting: permutations, binomial coefficients, Newton's Binomial Theorem, combinatorial proofs.
- Some practice problems from the Lehman-Leighton-Meyer textbook: 14.11, 14.15, 14.25, 14.28, 14.31.

- January 21:
- Counting: Combinatorial proofs.
- Some practice problems from the Lehman-Leighton-Meyer textbook: 14.7, 14.23, 14.57.

- January 23:
- Recursion.
- Here are some practice problems.

- January 28:
- Recursion.
- Here are some practice problems.

- January 30:
- Recursion.

- February 4:
- Recursion.

- February 6:
- Dining Cryptographers, sample spaces and probability functions.

- February 11:
- Basic rules of probability, uniform probability spaces.
- Here are some practice problems.
- Some practice problems from the Lehman-Leighton-Meyer textbook: 16.2(a), 16.2(b), 16.2(c).

- February 13:
- Birthday paradox, find the big box.
- Some practice problems from the textbook: 16.2(a), 16.2(b), 16.2(c).

- February 17-21: Reading week.
- February 25:
- Let's Make a Deal, the Monty Hall Problem.
- Conditional probability, independent events.
- Practice problem from the Lehman-Leighton-Meyer textbook: 17.12.
- Here is a practice problem.

- February 27: Midterm
- Answers midterm: 2d, 3b, 4a, 5a, 6b, 7c, 8b, 9d, 10a, 11b, 12a, 13c, 14d, 15a, 16b, 17b
- For Q7, the answer is (25 choose 16) times 7^9 times 21^16. Since 21 = 3 times 7, the correct answer is C.
- For Q1, all given answers are wrong, so
everybody gets 1 mark for this question. I thought that C was
the correct answer, but there is double-counting going
on in answer C. The correct answer is

(m choose 3) (n choose 2) (k choose 2) +

(m choose 2) (n choose 3) (k choose 2) +

(m choose 2) (n choose 2) (k choose 3) - For the midterm, you have to know everything we did in class up to and including February 13, as well as the first two assignments.
- To get an idea what to expect, here is the midterm from last term; the correct answers are: 1C, 2B, 3C, 4B, 5D, 6D, 7A, 8C, 9A, 10B, 11D, 12C, 13A, 14C, 15D, 16C, 17B
- Here are some old exam questions from (the old version of) COMP 1805; the correct answers are: 1A, 2B, 3D, 4C, 5C, 6A, 7D, 8C, 9C, 10D, 11A
- Here and here are the first two assignments from last term, and here and here are the solutions.

- March 4:
- Independent events.
- Practice problems from the Lehman-Leighton-Meyer textbook: 17.1, 17.5(a)+(b), 17.9.
- Here are some practice problems.

- March 6:
- Independent events.

- March 11:
- Infinite probability spaces.
- Here are some practice problems.

- March 13:
- Random variables, independent random variables.
- Here is a practice problem.

- March 18:
- Distribution functions, expected value, linearity of expectation.

- March 20:
- Geometric distribution and its expected value, binomial distribution and its expected value, indicator random variables.
- Practice problems from the Lehman-Leighton-Meyer textbook: 18.9, 18.10.
- Here are some practice problems.

- March 25:
- March 27:
- Skip Lists.
- Here are some practice problems.

- April 1:
- Skip lists, the probabilistic method (large bipartite subgraphs).
- Here is a practice problem.

- April 3:
- The probabilistic method.
- Here are all notes in one file.

- April 8:
- 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: