This page will be updated frequently with current and upcoming topics.
References to the recommended textbooks are made as follows: [LLM] is the Lehman-Leighton-Meyer book, and [Ros] is the Rosen book. Thus, for example, the notation [LLM:4.1,4.2] means "sections 4.1 and 4.2 of the Lehman-Leighton-Meyer book."
| Date | Topics | References | Due |
|---|---|---|---|
| Sep 15 | Course introduction; Three highlights of Discrete Mathematics | Slides | |
| Sep 17 | Pancakes with a problem | Slides | |
| Sep 18 x | Quiz 0 | — | |
| Sep 19 | Sets and operations on sets | Slides; [LLM:4.1,4.2] [Ros:2.1,2.2] | |
| Sep 22 | Relations and functions | Slides; [LLM:4.3,4.4,4.5] [Ros:2.3] | |
| Sep 24 | Quiz 0 discussion; Functions; Logic & logical notation | Slides; [LLM:3.1,3.2,3.3] [Ros: 1.1,1.2,1.3] | |
| Sep 25 x | (not used) | — | HW1 |
| Sep 26 | Logic: variables and quantifiers | Slides; [LLM:3.4,3.6] [Ros: 1.4,1.5] | |
| Sep 29 | Counting: disjoint union, arithmetic series | Notes; [Ros: 6.1] | |
| Oct 1 | Counting: product rule; mathematical induction | Notes; [LLM: 14.1,14.2,5.1] [Ros: 6.1,5.1] | |
| Oct 2 x | (not used) | — | HW2 |
| Oct 3 | Induction revisited; permutations | Notes; [LLM: 14.3,5.1] [Ros:6.1,5.1] | — |
| Oct 6 | Division rule; counting subsets | Notes; [LLM: 14.4,14.5] [Ros:6.3] | |
| Oct 8 | Binomial coefficients; bijective proofs | Notes; [LLM:14.6.3,14.10] [Ros:6.4] | |
| Oct 9 x | Midterm 1 (18:00-21:00) | — | |
| Oct 10 | The inclusion-exclusion principle | Notes; [LLM:14.9] [Ros:8.5] | HW3 |
| Oct 13 | Probability; sample spaces, events | Notes; [LLM:16.1,16.2,16.3] [Ros:7.1] | |
| Oct 15 | Probability: disjoint sum, inclusion-exclusion | Notes; [LLM:16.5] [Ros:7.1] | |
| Oct 16 x | Midterm 1 discussion | — | HW4 |
| Oct 17 | (no class; homecoming) | — | |
| Oct 20 | Conditional probability; four-step method | Notes; [LLM 17.1--17.4] [Ros:???] | |
| Oct 22 | Bayes's Theorem; independence | Notes; [LLM:17.5--17.8] [Ros:???] | |
| Oct 23 x | Random variables; expectation | Notes; [LLM:18.1,18.2] [Ros:???] | HW5 |
| Oct 24 | Linearity of expectation | Notes; [LLM:18.4,18.5] [Ros:???] | |
| Oct 27 | Independent variables; Variance | Notes; [LLM:18.2,19.3,19.4] [Ros:???] | |
| Oct 29 | Graphs, digraphs, degrees, handshake lemma; Pigeonhole principle | Notes; | |
| Oct 30 x | (not used) | — | HW6 |
| Oct 31 | Walks and paths; Connectivity; Equivalence relations | Notes; | |
| Nov 3 | Trees and the Tree Theorem | Notes | |
| Nov 5 | More on trees | Notes | |
| Nov 6 x | Midterm 2 (18:00-21:00) | — | |
| Nov 7 | Bipartite graphs | Notes | HW7 |
| Nov 10 | Directed graphs and partial orders | Notes | |
| Nov 12 | Matchings and marriages | Notes | |
| Nov 13 x | (not used) | — | |
| Nov 14 | Planarity and coloring; Euler's theorem | Slides & Notes | HW8 |
| Nov 17 | The five-color theorem | Notes |