CS 2800: Discrete Structures

Important information

Schedule

For upcoming lectures, I encourage you to consult the corresponding sections of last semester's lecture notes.

Topic Date Lecture topic
Basics 1/25 Introduction
1/27 Modeling problems
1/30 Quantifiers and proofs
Functions and relations 2/1 Functions, inverses, 'jectivity
2/3 Cardinality
2/6 Relations
2/8 Equivalence classes
2/10 Combinatorics
2/13 Constructing reals
2/15 Induction
2/17 Combinatorics II
Probability 2/22 Probability spaces
2/24 Conditional probability
2/27 Random variables
2/29 Combining random variables
3/3 Variance, probability bounds
3/6 Chebychev's inequality, Weak law of large numbers
3/8 Proof techniques review
3/9 7:30–9:00PM Prelim 1 (study guide)
3/10 Probabilistic counting
Automata 3/13 Inductive definitions
3/17 Structural induction
3/20 Finite automata
3/22 Automata constructions
3/24 Pumping lemma
3/27 Non-determinism
3/29 Regular expressions
3/31 Kleene's theorem
4/10 Turing machines
4/13 7:30–9:00PM Prelim 2 (study guide)
Number theory 4/12 Euclidean division
4/14 Strong induction, number bases
4/17 Euclid's GCD algorithm, modular numbers
4/19 Modular addition, multiplication, division
4/21 Modular exponentiation, Euler's theorem
4/24 RSA
Graphs 4/26 Basic definitions, handshaking theorem
4/28 Eulerian and Hamiltonian circuits
5/1 Coloring
Formal logic 5/3 Propositional logic
5/5 Proofs
5/8 Soundness and completeness
5/10 First-order logic, Gödel's theorem.
5/16, 2PM Final exam (study guide)

Office hours schedule (click for location)