- Attending all assigned classes

- Taking complete and legible notes

- Typing up lecture notes and submitting them electronically within 48-hours after each Class (handwritten notes can be scanned at the Notetaking Office)

- Maintaining confidentiality

Incentives include:

- A Co-Curricular Record (CCR) which recognizes student involvement on campus and is an official university document that can be printed through Carleton Central to present to potential employers. The CCR can be applied for at the end of each term through Carleton Central.

- A letter of appreciation that outlines the course(s) and duties that are performed by volunteer notetakers. An email will be sent outlining when a letter of appreciation can be requested directly from the PMC

Interested students should email the volunteer notetaking coordinator (volunteer_notetaking@carleton.ca) or stop by the Notetaking Office located in 501 University Centre (Paul Menton Centre).

Thank You.

Winter 2015

- Farah Chanchary, office hours: Thursday 9-11.
- Lei Chen, office hours: Monday 10:15-11:15.
- Alina Shaikhet, office hours: Wednesday 10-noon.
- Ruba Skaik, office hours: Tuesday and Thursday, 10:15-11:15.
- Andrew Trenholm, 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.
- 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.

- 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:
- Recursion: cutting a circle into regions, Section 4.6.

- February 10:
- 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 12:
- Basic rules of probability, uniform probability spaces, birthday paradox, Sections 5.3, 5.4, 5.5.

- February 16-20: Reading week.
- February 24: Midterm
- February 26:
- Birthday paradox, find the big box, Sections 5.5, 5.6.

- March 3:
- Let's Make a Deal, the Monty Hall Problem, Section 5.7.
- Conditional probability, Section 5.8.
- Independent events, Section 5.9.

- March 5:
- Independent events, Sections 5.9, 5.10.
- Choosing a random element in a linked list, Section 5.12.

- March 10:
- Long runs in random bitstrings, Section 5.13.
- Law of total probability, Section 5.11.

- March 12:
- Law of total probability, Section 5.11.
- 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.

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: