For upcoming lectures, I encourage you to consult the corresponding sections of last semester's lecture notes.
| Topic | Date | Lecture topic |
|---|---|---|
| Basics | 8/23 | Introduction |
| 8/25 | Modeling problems | |
| 8/28 | Proofs | |
| Probability | 8/30 | Probability intro |
| 9/1 | Conditional probability | |
| 9/6 | Independence | |
| 9/8 | More on proofs | |
| 9/11 | Random variables | |
| 9/13 | Expectation and variance | |
| 9/15 | Markov's, Chebychev's, Weak law of large numbers | |
| 9/18 | Probabilistic counting | |
| Functions and relations | 9/20 | Cardinality definitions |
| 9/22 | Inverses | |
| 9/25 | Cardinality and countability | |
| 9/27 | Uncountable sets | |
| 9/29 | Finite cardinality | |
| 10/2 | Induction | |
| 10/4 | Relations | |
| 10/6 | Equivalence classes | |
| Automata | 10/11 | Inductively defined sets |
| 10/13 | Structural induction; automata intro | |
| 10/16 | The language of a machine | |
| 10/18 | Union of recognizable sets | |
| 10/20 | Unsolvable problems | |
| 10/23 | Nondeterministic automata | |
| 10/25 | Regular expressions (last semester's notes) | |
| 10/27 | Kleene's theorem: RE to ε-NFA (last semester's notes) | |
| 10/30 | Kleene's theorem: NFA to RE (last semester's notes) | |
| 11/1a | Turing machines (last semester's notes) | |
| Number theory | 11/1b | Euclidean division (last semester's notes) |
| 11/3 | Strong induction, number bases (last semester's notes) | |
| 11/6 | modular numbers (last semester's notes: Modular numbers, arithmetic) | |
| 11/8 | Euler's theorem (last semester's notes) | |
| 11/10 | Properties of GCD | |
| 11/13 | RSA | |
| Formal logic | 11/15 | Formal logic, semantics |
| 11/17 | Proofs | |
| 11/20 | Soundness and completeness | |
| 11/27a | Completeness | |
| Graphs | 11/27b | Graph definitions, handshaking |
| 11/29 | Eulerian and Hamiltonian cycles | |
| 12/01 | ||
| Exams | 9/26 | Prelim 1 (7:30 PM in Statler 185) (study guide) |
| 10/26 | Prelim 2 (7:30 PM in Statler 185) (study guide) | |
| 12/8 | Final exam (9:00 AM in Statler 185) (study guide) |