This is the course website for CS 2800, Spring 2019
 Instructor: Michael George. Office hours Monday 1:303:30, Friday 1112 in Gates 447
 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
 Please enroll in Gradescope to submit assignments. You should use your NetID as your "student ID". The course code is MZWXR3
 Be sure to frequently refer to the list of Useful pages
Schedule
Topic 
Date 
Lecture Topic

Sets and Proof techniques

1/23 
Introduction (summary slides, board)

1/25 
Set definitions (summary slides, board)

1/28 
Set constructions (summary slides, board)

1/30 
Proof techniques (summary slides, board)

2/1 
Quantifiers and negation (summary slides, board)

Functions and Relations

2/4 
Function definitions (summary slides, board)

2/6 
Jectivity and inverses (summary slides, board)

2/8 
Cardinality (summary slides, board)

2/11 
Diagonalization (summary slides, board)

2/13 
Quantifier review (summary slides, board)

2/15 
Relations (summary slides, board)

2/18 
Equivalence classes (summary slides, board)

Number theory

2/20 
Induction (summary slides, board)

2/22 
Strong induction and Euclidean division (summary slides, board)

Break

2/25 
No class; February break


2/27 
Base b representation (summary slides, board)

3/1 
GCD algorithm (summary slides, board)

3/4 
Modular numbers (summary slides, board)

3/6 
Modular division and exponentiation (summary slides, board)

Exam

3/7 
Prelim 1 (study guide)


3/8 
Euler’s theorem (summary slides, board)

3/11 
Public key cryptography (summary slides, board)

Category:Automata

3/13 
Structural induction (summary slides, board)

3/15 
Deterministic Finite Automata (summary slides, board)

3/18 
Automata constructions (summary slides, board)

3/20 
Unrecognizable languages (summary slides, board)

3/22 
Pumping Lemma; Nondeterminism (summary slides, board)

3/25 
Removing nondeterminism (summary slides, board)

3/27 
Regular expressions (summary slides, board)

3/29 
Kleene's theorem (summary slides, board)

Break

4/1 
No class; Spring break

4/3 
No class; Spring break

4/5 
No class; Spring break

Category:Combinatorics

4/8 
Sum and product rule (summary slides, board)

4/10 
Permutations and combinations (summary slides, board)

Exam

4/11 
Prelim 2 (study guide)


4/12 
Combinatorial proofs (summary slides, board)

Category:Probability

4/15 
Probability spaces (summary slides, board)

4/17 
Conditional probability (summary slides, board)

4/19 
Random variables (summary slides, board)

4/22 
Expectation (summary slides, board)

4/24 
Variance (summary slides, board)

4/26 
Markov's/Chebychev's/Weak law (summary slides, board)

4/29 
Hashing (summary slides, board)

Category:Metalogic

5/1 
Propositional formulas and semantics (summary slides, board)

5/3 
Proofs (summary slides, board)

5/6 
Soundness and completeness (summary slides, board)

Exam

5/17 
Final exam: 2PM; Barton Hall (study guide)

Office hours schedule
(Click for location)