The Paul Menton Centre for Students with Disabilities is looking for a Volunteer Notetaker for this class. The criteria for being a Volunteer Notetaker include:

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

Discrete Structures II (COMP 2804)
Winter 2015

Instructor: Michiel Smid
Office: Herzberg Building 5125C
E-mail: michiel(@scs.carleton.ca)

Lectures: Tuesday/Thursday, 1:05-2:25pm, Azrieli Theatre 101

Office hours: Tuesday, 9-11am

Teaching assistants:

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.

Course objectives: A second course that is designed to give students a basic understanding of Discrete Mathematics and its role in Computer Science. Computers handle discrete data rather than continuous data. The course presents an overview of some of the major theoretical concepts needed to analyze this type of data.

Topics covered include: Counting, sequences and sums, discrete probability, basic statistics, recurrence relations, randomized algorithms. Material is illustrated through examples from computing.

Textbook:

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.

Important dates:

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

Grading scheme:

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

Assignments:

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.
- Here is Assignment 1 as a pdf file.
- Here is the LaTeX file.
- Here are the solutions.
- The marks will be posted on cuLearn; they are out of 50. Breakdown of the marks: Q2: 3+3=6, Q3: 7, Q4: 7, Q5: 4+4=8, Q6: 3, Q7: 1+3+3=7, Q8: 6, Q9: 6
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.

What was done in class:

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.

Tentative schedule (based on fall 2014 term):

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.

Undergraduate Academic Advisor:

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.

University Policies:

Student Academic Integrity Policy: Every student should be familiar with the Carleton University student academic integrity policy. A student found in violation of academic integrity standards may be awarded penalties which range from a reprimand to receiving a grade of F in the course or even being expelled from the program or University. Some examples of offences are: plagiarism and unauthorized co-operation or collaboration. Information on this policy may be found in the Undergraduate Calendar.

Plagiarism: As defined by Senate, "plagiarism is presenting, whether intentional or not, the ideas, expression of ideas or work of others as one's own". Such reported offences will be reviewed by the office of the Dean.

Unauthorized Co-operation or Collaboration:

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.

Equity Statements:

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

Pregnancy obligation: write to me with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details visit the Equity Services website: http://www2.carleton.ca/equity/

Religious obligation: write to me with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details visit the Equity Services website: http://www2.carleton.ca/equity/

Academic Accommodations for Students with Disabilities: The Paul Menton Centre for Students with Disabilities (PMC) provides services to students with Learning Disabilities (LD), psychiatric/mental health disabilities, Attention Deficit Hyperactivity Disorder (ADHD), Autism Spectrum Disorders (ASD), chronic medical conditions, and impairments in mobility, hearing, and vision. If you have a disability requiring academic accommodations in this course, please contact PMC at 613-520-6608 or pmc@carleton.ca for a formal evaluation. If you are already registered with the PMC, contact your PMC coordinator to send me your Letter of Accommodation at the beginning of the term, and no later than two weeks before the first in-class scheduled test or exam requiring accommodation (if applicable). After requesting accommodation from PMC, meet with me to ensure accommodation arrangements are made. Please consult the PMC website for the deadline to request accommodations for the formally-scheduled exam (if applicable) at http://www2.carleton.ca/pmc/new-and-current-students/dates-and-deadlines/ You can visit the Equity Services website to view the policies and to obtain more detailed information on academic accommodation at http://www2.carleton.ca/equity/

Medical Certificate: The following is a link to the official medical certificate accepted by Carleton University for the deferral of final examinations or assignments in undergraduate courses. To access the form, please go to http://www1.carleton.ca/registrar/forms/

Discrete Structures II (COMP 2804) Winter 2015

Discrete Structures II (COMP 2804)
Winter 2015