Weekly Schedule (tentative)
Week |
Topics |
Assigned reading |
Homework |
8/23-8/27 |
Introduction, DFAs, NFAs, closure properties |
Chapter 0, Chapter 1 (till page 54) |
Homework 0, Homework 1 |
8/30-9/03 |
NFAs, determinization: subset construction, closure properties |
Chapter 1 till page 66 |
Homework 2 |
9/06-9/10 |
Regular expressions, Non-regular languages |
Chapter 1, till Section 1.3 |
Homework 3 |
9/13-9/17 |
Pumping lemma and non-regular languages, Myhill-Nerode theorem |
Chapter 1 |
Homework 4 |
9/20-9/24 |
Characterizing non-regular languages, DFA minimization, Context-free grammars |
Section 2.1 |
Homework 5 |
9/27-10/01 |
Pushdown automata, review |
Section 2.2 |
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 |
|
|