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 | |