Discrete Structures II (COMP 2804)
Office: Herzberg Building 5125C
Lectures: Wednesday/Friday 8:35am-9:55am,
Minto Centre 2000
Office hours: Wednesday 10:15am-noon
- Location TA's office hours: Herzberg Building 5336
- Tri Cao
Office hours: Monday 3-5
- Alexa de Grandmont
Office hours: Friday 10-noon
- Zoltan Kalnay
Office hours: Tuesday 10-noon
- Yingjie Song
Office hours: Monday 10:30-12:30
- Tyler Tuttle
Office hours: Thursday 2-4
- Yuan Wu
Office hours: Thursday 10-noon
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.
- The following free textbook will be used:
Discrete Structures for Computer Science: Counting, Recursion, and
- 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 Thursday September 13,
due Sunday September 30
- Assignment 2: posted Sunday September 30,
due Sunday October 14
- Midterm: Friday October 19 (in class)
- Assignment 3: posted Thursday November 1,
due Thursday November 15
- Assignment 4: posted Thursday November 15,
due Thursday November 29
- Final exam: TBA
- Assignments: 25%
- Midterm: 25%
- Final exam: 50%
- 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.
- Each assignment must be submitted as one single PDF file through
- 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
- Instructions on how to submit your assignment can be found
- Assignment 1 is due Sunday September 30, before 11:55pm.
- The assignment has been updated: In Q5, the variables f, m, and k
are all at least 2.
- Here is Assignment 1 as a
- Here is the LaTeX file,
here is the figure.
- I used the freely available
drawing editor to make the figure.
- Here are the solutions.
- Assignment 2 is due Sunday October 14, before 11:55pm.
- Here is Assignment 2 as a
- Here is the LaTeX file.
- Here are the solutions.
- Here you
find assignments from previous terms.
- Here you
find midterms from previous terms.
- Exams from previous terms will be posted here.
- For the midterm, you have to know everything we did in class up to
and including the birthday paradox, as well as the first two
- Calculators are allowed.
- Bring pencils (the scantron machine prefers pencils).
- Information about the final exam will be posted here.
What was done in class:
- September 5:
- Course overview. Chapter 1 in the textbook:
- 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.
- September 7:
- September 12:
- September 14:
- September 19:
- September 21:
- Pigeonhole Principle, Exercises 3.69 and 3.71, Section 3.10.1.
Recursion: recursive functions, Section 4.1.
- September 26:
- September 28:
- Recursion: Euclid's algorithm.
- October 3:
- Recursion: Running time of MergeSort, Section 4.5.
- Recursion: Exercise 4.59, my notes are
- October 5:
- October 10:
- Basic rules of probability, Section 5.3.
- Uniform probability spaces, Section 5.4.
- Exercise 5.10, which is
known as the
Newton Pepys problem.
- October 12:
Tentative schedule (based on last term; some section numbers may
- October 17:
- October 19: Midterm
- October 22-26: Fall break
- October 31:
- Pairwise and mutually
independent events, Section 5.11.3, Exercise 5.61,
- The probability of a circuit failing, Section 5.12.3.
- November 2:
- Choosing a random element in a linked list, Section 5.13.
- Long runs in random bitstrings, Section 5.14.
- November 7:
- Infinite probability spaces, Section 5.15, Exercises 5.63 and
- November 9:
- November 14:
- November 16:
- November 21:
- Indicator random variables, Section 6.8, Exercises 6.29 and
- November 23:
- November 28:
- November 30:
- Analysis of skip lists, Section 6.11.3.
- December 5:
- Solutions midterm and old exam.