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
Quiz #1
Regular languages and their closure properties
Reading: Hammack 4
Exercises #2 due
Week 3
Regular expressions
Reading: Sipser 1.3
Quiz #2
Snow day!
No reading.
Week 4
Nonregular languages
Reading: Sipser 1.4, Hammack 5
Quiz #3 online
Context-free grammars
Reading: Sipser 2.1 slides
Week 5
Context-free languages and their closure properties
Reading: Hammack 6, intersection of CF and regular languages
Quiz #4
Exercises #3 due
Non–context-free languages
Reading: Sipser 2.3
Week 6
Exam 1
No reading.
Problem set #2 due
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
Quiz #5
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
Diagonalization and the halting problem
Reading: Sipser 4.2
Quiz #6
Undecidable languages
No reading.
Exercises #5 due
Week 10
Reductions
Reading: Sipser 5.1
Quiz #7
Mapping reductions
Reading: Sipser 5.3
Problem set #3 due
Week 11
Exam 2
No reading.
Time complexity
Reading: Sipser 7.1
Week 12
Polynomial time 1
Reading: Sipser 7.2
Polynomial time 2
Reading: Sipser 7.3
Quiz #8; Exercises #6 due
Week 13
Nondeterministic polynomial time
Reading: Sipser 7.4
NP-completeness 1
Reading: Sipser 7.5
Quiz #9; Exercises #7 due
Week 14
NP-completeness 2
No reading.
Quiz #10
NP-completeness 3
No reading.
Problem set #4 due
Final Exam