Week | Topics | Assigned reading | Homework |
---|---|---|---|
8/22-8/26 | Introduction, DFAs, NFAs, closure properties | MCS:Chapter 1, MCS: Sections 4.1,4.2,4.3; Chapter 0, Chapter 1 (till page 54) |
Homework 0, Homework 1 |
8/29-9/02 | NFAs, determinization: subset construction, closure properties, regular expressions |
Chapter 1 till page 66 | Homework 2, Prereq Quiz (Sets, Propositional logic) |
9/05-9/09 | CS220 revisit (Sets, Propositional logic), Regular expressions, non-regular languages |
Chapter 1, till Section 1.3 | Homework 3 |
9/12-9/16 | Pumping lemma and non-regular languages, Characterizing non-regular languages, first order logic |
Chapter 1 | Homework 4 |
9/19-9/23 | First order logic Henkin-Hintikka evaluation games, DFA minimization |
Gersting:Sections 1.2, 1.3 | Homework 5 |
9/26-9/30 | Myhill-Nerode Theorem, Context-free grammars, review | Section 2.1 | Midterm prep |
10/03-10/05 | Midterm 1, Pushdown automata | Section 2.2 | Homework 6 |
10/10-10/14 | Midterm 1 solutions, PDA-CFG equivalence | Section 2.3 | Homework 7 |
10/17-10/21 | Pumping lemma for CFLs, CYK algorithm, Turing machines | Chapter 3 | Homework 8 |
10/24-10/28 | Non-deterministic Turing machines, Undecidability | Chapter 4 | Homework 9 |
10/31-11/04 | Undecidability, Turing reducibility | Sections 5.1, 6.3 | Midterm prep |
11/07-11/11 | Review, Midterm 2 (comprehensive) | Midterm prep | |
11/14-11/18 | Many-one reducibility | Section 5.3 | Homework 10 |
11/28-12/02 | Midterm solutions, theories in first order logic, arithmetic heirarchy | Homework 11 | |
12/05-12/09 | Review | ||
12/12-12/16 | Final exam (open book) |