Topic 
Date  Lecture summary  Additional material 
Basic tools 
8/26 
Introduction to CS2800, Functions 
8/28 
Creating definitions 

Cardinality 
8/31 
Cardinality 
9/2 
Countability 

9/4 
Uncountable sets, halting problem 
Functions 
9/9 
Inverses 

9/11 
Relations 
Probability 
9/14 
Probability definitions 

9/16 
Probability 
9/18 
Probability 
9/21 
Markov and Chebychev 
9/23 
Law of large numbers 
9/25 
Random graphs 
9/28 
Random algorithms 
Prelim 
9/30 
Logic review 
10/2 
Prelim 1 

Number theory 
10/5 
Bases and division 
10/7 
Strong induction, Euclid's algorithm 

10/9 
Congruence mod m 

10/12 
No class (enjoy your break!) 
Regular languages 
10/14 
Regular expressions 
10/16 
Finite automata 

10/19 
Nondeterminism 
10/21 
NFA = DFA = RE 
Modular arithmetic 
10/23 
Equivalence classes 
10/26 
Modular arithmetic 
10/28 
Euler's theorem 
10/30 
RSA 
Prelim 
11/2 
Prelim 2 


11/4 
RSA Example 
11/6 
Signing, prelim review 

11/9 
Structural induction 
More automata 
11/11 
Pumping lemma 
 Hopcroft and Ullman.
Introduction to Automata Theory, Languages, and Computation

11/13 
Context free grammars 
11/16 
Turing machines 
11/18 
Recursive sets 
11/20 
Halting problem 
11/23 
NP completeness 


Happy thanksgiving! 
Logic 
11/30 
Propositional logic 

12/2 
12/4 
Future 
12/17  9:00 AM, Final  