This is the course website for CS 2800, Spring 2020.
 Instructor: Michael George. Office hours Wednesday 35 in Ward B01.
 Class meets Monday, Wednesday, Friday, 10:1011:00am in Statler 185
 Please read the syllabus
 Please enroll in Piazza for all course announcements and discussion
 Homework is posted on Piazza
 Be sure to frequently refer to the list of Useful pages
Schedule
You are responsible for learning the material in the "prep" page before the corresponding lecture. The prep page will also contain a link to the previous semester's notes. If you want to look ahead to lectures where I haven't yet posted the prep page, you can visit the CS 2800 Fall 2019 page.
Topic 
Date 
Lecture Topic

Sets and Proof techniques

1/22 
Introduction (prep, slides)

1/24 
Set definitions (prep, slides)

1/27 
Set constructions (prep, slides)

1/29 
Proof techniques (prep, slides)

Functions and Relations

1/31 
Functions (prep, slides)

2/3 
Quantifiers (prep, slides)

2/5 
'Jectivity and inverse functions (prep, slides)

2/7 
Cardinality (prep, slides)

2/10 
Diagonalization (prep, slides)

2/12 
Relations (prep, slides)

2/14 
Equivalence classes (prep, slides)

Number theory

2/17 
Induction (prep, slides)

2/19 
Strong induction and Euclidean division (prep, slides)

2/21 
Base b representation (prep, slides)


2/24 
No class; February break

Number theory

2/26 
GCD algorithm (prep, slides)

2/28 
Bézout coefficients (prep, slides)

3/2 
Modular numbers (prep, slides)

3/4 
Modular division and exponentiation (prep, slides)


3/5 
Prelim 1 (study guide)

Number theory

3/6 
Euler’s theorem (prep, slides)

3/9 
Public key cryptography (prep, slides)

3/11 
RSA (prep, slides)

Category:Automata

3/13 
Inductively defined sets (prep, slides)

3/16 
Structural induction (prep, slides)

3/18 
Deterministic Finite Automata (prep, slides)

3/20 
Automata constructions (prep, slides)

3/23 
Unrecognizable languages (prep, slides)

3/25 
Nondeterminism (prep, slides)

3/27 
Regular expressions (prep, slides)


3/30 
No class; Spring break

4/1 
No class; Spring break

4/3 
No class; Spring break

Category:Automata

4/6 
Kleene's theorem (prep, slides)

Category:Combinatorics

4/8 
Sum and product rule (prep, slides)


4/9 
Prelim 2

Category:Combinatorics

4/10 
Permutations and combinations (prep, slides)

4/13 
Combinatorial proofs (prep)

Category:Probability

4/15 
Probability spaces (prep)

4/17 
Conditional probability (prep)

4/20 
Random variables (prep)

4/22 
Expectation (prep)

4/24 
Independent RVs (prep)

4/27 
Markov's/Chebychev's/Weak law (prep)

Category:Metalogic

4/29 
Truth tables (prep)

5/1 
Proof trees (prep)

5/4 
Soundness and completeness (prep)


5/15 
2:00 Final exam

Office hours schedule
(Click for location)