Discrete Structures II (COMP 2804)
Office: Herzberg Building 5125C
Lectures: Monday/Wednesday, 10:05am-11:25am, University Centre 231
Office hours: Tuesday, 10-noon
- Yaser Alwattar
Office hours: Tuesday noon-2pm
- Farah Chanchary
Office hours: Monday 1:30-3:30pm
- Kimberly Crosbie
Office hours: Tuesday 1-3pm
- Omar Ben Ismail
Office hours: Thursday 1:30-3:30pm
- Sehwan Lee
Office hours: Wednesday 2-4pm
- Rui Li
Office hours: Monday 5:30-7:30pm
- Nicolas Perez
Office hours: Friday 11am-1pm
- The TAs have their office hours in Herzberg Building 1170.
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.
- Assignment 1: posted January 18, due February 1
- Assignment 2: posted February 1, due February 15
- Assignment 3: posted March 8, due March 22
- Assignment 4: posted March 22, due April 5
- Midterm: Wednesday March 1 (in class)
- Final exam: TBA
- Assignments: 25%
- Midterm: 25%
- Final exam: 50%
- Late assignments will not be accepted.
- Will be posted here.
What was done in class:
- January 9:
- 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.
- January 11:
- January 16:
Sections 3.2, 3.3, 3.4, 3.5, 3.6.
Tentative schedule (based on the fall 2016 term; section numbers in
the textbook have changed):
- January 18:
- January 23:
- January 25:
- Counting solutions of linear equations and inequalities,
Pigeonhole Principle, Section 3.10.1.
Recursion: recursive functions,
- January 30:
- Recursion: Counting 00-free bitstrings, gossip problem,
Sections 4.2.1, 4.4.
- February 1:
- February 6:
- Recursion: cutting a circle into regions, Sections 4.6.1, 4.6.2.
- February 8:
- Recursion: cutting a circle into regions, Section 4.6.
- Anonymous broadcasting:
Dining Cryptographers, Section 5.1.
- February 13:
- February 15:
- uniform probability spaces,
birthday paradox, Sections 5.4, 5.5.
- Find the big box, Section 5.6.
- February 20-24: Winter break
- February 27:
- March 1: Midterm
- March 6:
- March 8:
- March 13:
- The probability of a circuit failing, Section 5.11.3.
- Choosing a random element in a linked list, Section 5.12.
- Infinite series, Section 5.14.1.
- March 15:
- March 20:
- Independent random variables, Section 6.2.
Expected value, Section 6.4.
- March 22:
- March 27:
- Indicator random variables, Section 6.8, Exercise 6.31.
- Estimating the
harmonic number, Section 6.8.3.
- Expected running time of
Insertion-Sort, Section 6.9.
- March 29:
- Expected running time of Insertion-Sort, Section 6.9.
- Expected running time of
- April 3:
- Skip lists,
- Probabilistic method: large bipartite subgraphs, Section 7.1.
- April 5:
- Solutions midterm and previous exam.