This is the course website for CS 2800, Spring 2019
- Instructor: Michael George. Office hours Monday 1:30-3:30, Friday 11-12 in Gates 447
- Class meets Monday, Wednesday, Friday, 10:10-11: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)