Week 1
Introduction
Reading: Sipser 0, Hammack 1 & 2
Deterministic finite automata
Reading: Sipser 1.1
Exercises #1 due
Week 2
Nondeterministic finite automata
Reading: Sipser 1.2
Regular languages and their closure properties
Reading: Hammack 4
Exercises #2 due
Week 3
Regular expressions
Reading: Sipser 1.3
Nonregular languages and the pumping lemma
Reading: Sipser 1.4
Problem set #1 due on the 15th
Week 4
Proving that a language is nonregular
Reading: Hammack 5
Context-free grammars
Reading: Sipser 2.1
Exercises #3 due
Week 5
Context-free languages and their closure properties
Reading: Hammack 6, intersection of CF and regular languages
Non–context-free languages
Reading: Sipser 2.3
Problem set #2 due on the 2nd
Week 6
Exam 1
No reading.
Turing machines; languages and input encoding
Reading: Sipser 3.1
Week 7
Turing machine variants and the Church-Turing thesis
Reading: Sipser 3.2 and 3.3
Decidable languages
Reading: Sipser 4.1
Exercises #4 due
Week 8
Spring break: No class
No reading.
Spring break: No class
No reading.
Week 9
Decidable languages
Reading: Sipser 4.1
Exercises #4 due
Diagonalization and the halting problem
Reading: Sipser 4.2
Week 10
Undecidable languages
No reading.
Reductions
Reading: Sipser 5.1
Problem set #3 due on the 6th
Week 11
Exam 2
No reading.
Mapping reductions
Reading: Sipser 5.3
Week 12
Time complexity
Reading: Sipser 7.1
Polynomial time
Reading: Sipser 7.2
Exercises #5 due
Week 13
Nondeterministic polynomial time
Reading: Sipser 7.3
NP-completeness 1
Reading: Sipser 7.4
Exercises #6 due
Week 14
NP-completeness 2
Reading: Sipser 7.5
NP-completeness 3
No reading.
Problem set #4 due
Final Exam