Discrete Structures II (COMP 2804)
Office: Herzberg Building 5125C
Lectures: Monday/Wednesday, 8:35am-9:55am, River Building 2200
Office hours: Monday, 10am-noon
- Yaser Alwattar
Office hours: Tuesday, noon-2pm
- Ahmad Biniaz
Office hours: Friday, 1-3pm
- Farah Chanchary
Office hours: Thursday, 10-noon
- Kimberly Crosbie
Office hours: Tuesday, 1-3pm
- Sehwan Lee
Office hours: Wednesday, 10-noon
- 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, sequences and sums, discrete probability, basic statistics,
recurrence relations, randomized algorithms. Material is illustrated
through examples from computing.
- Assignment 1: posted September 21, due October 5
- Assignment 2: posted October 5, due October 19
- Assignment 3: posted November 9, due November 23
- Assignment 4: posted November 23, due December 7
- Midterm: Wednesday November 2 (in class)
- Final exam: TBA
- Assignments: 25%
- Midterm: 25%
- Final exam: 50%
- Late assignments will not be accepted.
- Assignment 1 is due Wednesday October 5, before 4:30pm, in the course
drop box in Herzberg 3115.
What was done in class:
- September 7:
- 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 12:
- September 14:
Sections 3.2, 3.3, 3.4, 3.5, 3.6.
- September 19:
- September 21:
- September 26:
- Counting solutions of linear equations and inequalities,
Pigeonhole Principle, Section 3.10.1.
Recursion: recursive functions,
Tentative schedule (based on fall 2015 term):
- September 28:
- Recursion: Counting 00-free bitstrings, gossip problem,
Sections 4.2.1, 4.4, 4.5.
- October 3:
cutting a circle into regions, Sections 4.5, 4.6.
- October 5:
- Recursion: cutting a circle into regions, Section 4.6.
- October 10:
- October 12:
- October 17:
- October 19:
- October 24-28: Fall break
- October 31:
- November 2: Midterm
- November 7:
- Independent events, Sections 5.10, 5.11.
- Choosing a random element in a linked list, Section 5.12.
- November 9:
- Exercise 5.35.
- Long runs in random bitstrings, Section 5.13.
- November 14:
- Infinite probability spaces, Section 5.14.
- November 16:
- November 21:
- November 23:
- Binomial distribution and its expected value, Section 6.7.
- Indicator random variables, Exercise 6.17 and Section 6.8.
- November 28:
- Where does Question 8 in Assignment 3 come from?
- Estimating the
harmonic number, Section 6.8.3.
- Expected running time of
Insertion-Sort, Section 6.9.
- November 30:
- December 5:
- Skip lists, Section 6.11.
- December 7:
- December 9:
- Solutions midterm. Please bring the midterm, so that I do not
have to write all questions on the board.