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/06-9/10 | CS220 revisit (Sets, Propositional logic), Regular expressions, Non-regular languages |
Chapter 1, till Section 1.3 | Homework 3 |
9/13-9/17 | Pumping lemma and non-regular languages, Characterizing non-regular languages, First order logic |
Chapter 1 | Homework 4 |
9/20-9/24 | First order logic Henkin-Hintikka evaluation games, DFA minimization |
Gersting:Sections 1.2, 1.3 | Homework 5 (optional) |
9/27-10/01 | Context-free grammars, Pushdown automata, review | Section 2.1 | Midterm prep |
10/04-10/08 | Midterm 1, PDA-CFG equivalence | Section 2.2 | Homework 6 |
10/11-10/15 | Midterm 1 solutions, pumping lemma for CFLs, CYK algorithm | Section 2.3 | |
10/18-10/22 | Turing machines, non-determinism | Chapter 3 | Homework 7 |
10/25-10/29 | Decidability, Reducibility | Chapter 4, Section 5.1 | Homework 8 |
11/01-11/05 | Reducibility | Sections 5.1, 5.3, 6.3 | |
11/08-11/12 | Reducibility, Review | Midterm preparation | |
11/15-11/19 | Midterm 2, Reducibility | Homework 9 | |
11/29-12/03 | First-order logic | Section 6.2, notes | Homework 10 |
12/06-12/10 | Midterm 2 solutions, review | ||
12/13-12/17 | Final exam |