Discrete Structures II (COMP 2804)
Fall 2014
Instructor:
Michiel Smid
Office: Herzberg Building 5125C
Email: michiel(@scs.carleton.ca)
Lectures: Wednesday and Friday, 8:359:55, Azrieli Theatre 102
Office hours: Tuesday, 911am
Teaching assistants:
 Farah Chanchary, office hours: Thursday 8:3010:30am
 Tommy Reddad, office hours: Wednesday 10noon.
 Peter Simonyi, office hours: Thursday noon2pm.
 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:
Important dates:
 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
Grading scheme:
 Assignments: 25%
 Midterm: 25%
 Final exam: 50%
Assignments:
 Late assignments will not be accepted.
 Assignment 1 is due October 1, before 23:59pm, in the course drop
box in Herzberg 3115.
 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: 10, Q3: 5, Q4: 5, Q5: 5, Q6: 3,
Q7: 3+3+3=9, Q8: 5, Q9: 8
 Assignment 2 is due October 15, before 23:59pm, in the course drop
box in Herzberg 3115.
 Here is Assignment 2 as a
pdf file.
 Here is the
LaTeX file and
here is the figure file.
 Here are the solutions.
 The marks will be posted on cuLearn; they are out of 50.
Breakdown of the marks: Q2: 5, Q3: 5, Q4: 7, Q5: 9, Q6: 7,
Q7: 3, Q8: 6, Q9: 8
What was done in class:
 September 5:
 Course overview. Chapter 1 in the textbook:
Ramsey Theory,
Sperner's Theorem,
QuickSort.
 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), Sigmanotation for summations, basic graph
theory, BigOh, BigOmega, BigTheta.
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:
 September 12:
 September 17:
 September 19:
 September 24:
 September 26:
 Recursion: recursive functions,
Fibonacci numbers,
a recursively defined set, Sections 4.1, 4.2, 4.3.
 October 1:
 Recursion: gossip problem,
MergeSort,
Sections 4.4, 4.5.
 October 3:
 Recursion: MergeSort, cutting a circle into regions,
Sections 4.5, 4.6.
 October 8:
 Recursion: cutting a circle into regions, Section 4.6.
 October 10:
 October 15:
 Basic rules of probability, uniform probability spaces,
birthday paradox, Sections 5.3, 5.4, 5.5.
 October 17:
 Birthday paradox, find the big box, Sections 5.5, 5.6.
 October 22:

October 24: Midterm
 For the midterm, you have to know everything we did in class
up to and including October 17, as well as the first two
assignments.
 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
 Answers midterm: 1c, 2c, 3d, 4d, 5a, 6c, 7b, 8a, 9b, 10c, 11b,
12c, 13d, 14c, 15a, 16a, 17d
Tentative schedule (based on winter 2014 term):
 October 2731: Reading week
 November 5:
 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 InsertionSort and QuickSort.
 November 26:
 November 28:
 Skip lists, the probabilistic method (large bipartite subgraphs).
 December 3:
 The probabilistic method.
 December 5:
 Review.
 Solutions midterm.
Undergraduate Academic Advisor:
The undergraduate advisor for the School of Computer Science is
available in Room 5302C HP, by telephone at 5202600, 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 cooperation 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 Cooperation 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 6135206608 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 inclass 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 formallyscheduled
exam (if applicable) at
http://www2.carleton.ca/pmc/newandcurrentstudents/datesanddeadlines/
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/