The course was based on the textbook
Discrete Mathematics and Its Applications, 7th Edition
by Kenneth H. Rosen.
| Week | Lectures |
Readings |
|---|
| 1 | Sep 16: Lecture 1: Introduction and Course Admin
Sep 18: Lecture 2:
Review of Propositional Logic
Sep 19: Lecture 3:
Predicate Logic
|
Rosen chapter 1 |
| 2 | Sep 23: Lecture 4: Proof techniques
Sep 25: Lecture 5:
Sets
Sep 26: Lecture 6:
Relations
|
Rosen chapters 1, 2 and 9 |
| 3 | Sep 30: Lecture 7: Functions
Oct 2: Lecture 8: Sequences, Sums, Cardinality
Oct 3: Lecture 9: Algorithms, part 1
|
Rosen chapters 2 and 9, then chapter 3 |
| 4 | Oct 7: Lecture 10: Algorithms, part 2
Oct 9: Lecture 11: Number theory, part 1
Oct 10: Lecture 12: Number theory, part 2
|
Rosen chapter 3, then chapter 4 |
| 5 | Oct 14: Lecture 13: Cryptography
Oct 16: Lecture 14: Induction
Oct 17: Lecture 15: Recursion and structural induction
|
Rosen chapter 4, then chapter 5 |
| 6 | Oct 21: Lecture 16: Basic Counting, and the Pigeonhole Principle
Oct 23: Lecture 17: Permutations
& Combinations, Binomial Coefficients
Oct 24: Lecture 18:
Generalized Permutations & Combinations
|
Rosen chapter 6 |
| 7 | Oct 28: Lecture 19: Graphs: basic
definitions and examples
Oct 30: Lecture 20: Bipartite
Graphs and Matching
Oct 31: Lecture 21:
Graph Isomorphism; Paths and Connectivity; Euler paths/circuits
|
Rosen chapter 10 |
| 8 |
Nov 4: Lecture 22:
Euler and Hamiltonian paths/circuits (continued);
shortest paths;
Nov 6:
Lecture 23: Shortest Paths and Dijkstra's algorithm; Graph Coloring
Nov 7:
Lecture 24: Trees
|
Rosen chapter 10 & 11 |
| 9 |
Nov 11: Lecture 25:
Introduction to Discrete Probability; some important distributions;
Nov 13:
Lecture 26: Conditional probabability; Bayes' theorem
Nov 14:
Lecture 27: Random variables, Expectation, and Variance
|
Rosen chapter 7 |
| 10 |
Nov 18: Lecture 28:
Markov's and Chebyshev's Inequalities; Examples in probability: the birthday problem;
Nov 20:
Lecture 29: Examples in probability: ramsey numbers
Nov 21:
Lecture 30: More examples in probability
|
Rosen chapter 7 |