Discrete Structures II (COMP 2804, Section B)
Fall 2020
Instructor:
Michiel Smid
Office: Herzberg Building 5125C (Note that it is unlikely that
we are allowed to enter Herzberg.)
Email: michiel(@scs.carleton.ca)
Lectures:
 Official meeting times: Wednesday and Friday, 4:05  5:25 pm.
 There won't be live lectures. Instead, links to prerecorded video
lectures will be posted in the section "What was done in class".
Fall term:
 First lecture is on Wednesday September 9.
 October 2630: Fall break, no classes.
 Last lecture is on Wednesday December 9.
 Friday December 11: Last day of classes in the fall term. Classes
follow a Monday schedule.
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, recursion, discrete probability, random variables,
randomized algorithms. Material is illustrated
through examples from computing.
Textbook:
Important dates:
 Assignment 1: due Sunday September 27 at 23:55
 Assignment 2: due Sunday October 11 at 23:55
 Midterm: Wednesday October 21, 16:00  17:30
 Assignment 3: due Sunday November 22 at 23:55
 Assignment 4: due Sunday December 6 at 23:55
 Final exam: Friday December 18, 9:00  11:00
Grading scheme:
 Assignments: 25%
 Midterm: 25%
 Final exam: 50%
Assignments:
 Late assignments will not be accepted.
 Real computer scientists use
LaTeX to type
their solutions. In case you want to learn LaTeX,
here is a tutorial.
 You can use the freely available
Ipe drawing
editor to make figures.
 Each assignment must be submitted as one single PDF file through
cuLearn.
 You can type your solutions, or write them by hand and scan them
(for example, using a scan app on your phone or using a real
scanner).
 Assignment 1 is due Sunday September 27, before 11:55 pm.
 Here is Assignment 1 as a
pdf file.
 Here is the LaTeX file.
 Here are the solutions.
 Assignment 2 is due Sunday October 11, before 11:55 pm.
 Here is Assignment 2 as a
pdf file.
 Here is the LaTeX file.
 Here are the solutions.
 Assignment 3 is due Sunday November 22, before 11:55 pm.
 Here is Assignment 3 as a
pdf file.
 Here is the LaTeX file and
here is the photo.
 Here are the solutions.
 Assignment 4 is due Sunday December 6, before 11:55 pm.
 Here is Assignment 4 as a
pdf file.
 Here is the LaTeX file.
 Here are the solutions.
Practice problems and old midterms/exams:
 Here you
find assignments from previous terms.
 Here you
find midterms from previous terms.
 Here you
find final exams from previous terms.
 Your TA Alexa de Grandmont, together with Matthew MacRaeBovell and
Forest Anderson, have developed the
Computer Science Study Center.
You will find interactive online versions of previous midterms for
this course. More material will be added.
Midterm:
 The midterm will be on Wednesday October 21, 16:00  17:30.
 Sign in to cuLearn on Wednesday October 21 by 16:00 and click the
midterm exam link to begin.
 You have to know everything that was done in the lectures up to, and
including, October 14, as well as the first two assignments.
Final exam:
 The final exam will be on Friday December 18, 9:00  11:00 am.
 Note that Carleton's Final Exam Schedule says that the exam will
be three hours. This is an error. The exam will be two hours.
 The format will be the same as for the midterm.
 Sign in to cuLearn on Friday December 18 by 9 am and click the
final exam link to begin.
 You have to know everything that was done in the lectures, as well
as all four assignments.
Academic Integrity (New, Please Read):
As of 2020, there are new penalties in place for academic integrity
violations. These will be issued by the Associate Dean (Undergraduate
Affairs) of Science to students who copy, in whole or in part, work
they submit for assignments.
 First offence, firstyear students (less than 4.0 credits completed):
No credit for assessment(s) in question, or a final grade reduction of
one full letter grade (e.g., A becomes B), whichever is a greater
reduction.
 First offence (anyone else): A grade of F in the course.
 Second offence (anyone): A grade of F in the course and a oneterm
suspension from studies.
 Third offence: Expulsion from the University.
Note: While these are the standard penalties, more severe penalties may
be applied when warranted. For more information, click
here.
What was done in class (chapter and section numbers refer to the
textbook):

Video lecture 0: Very short intro to the course.
 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 and do some
of the exercises at the end of that chapter.
 September 9:
 September 11:
 September 16:
 September 18:
 September 23:
 September 25:
 September 30:
 October 2:
 October 7:
 October 9:
 October 14:
 October 16:
 October 21: Midterm
 October 23:
 October 2630: Fall break.
 November 4:
 November 6:
 November 11:
 November 13:
 November 18:
 November 20:
 November 25:
 November 27:
 December 2:
 December 4:
 December 9:
Tentative schedule (based on the last time I taught this course)
 Friday December 11:
 No lecture: Classes follow a Monday schedule.