CSE 105: Automata and Computability Theory


Date Topic and reading
Thu, Sep. 24 Intro; mathematical preliminaries
Reading: Sipser 0
Homework #1 out
Tue, Sep. 29 Deterministic finite automata
Reading: Sipser 1.1
Thu, Oct. 1 Nondeterministic finite automata
Reading: Sipser 1.2
Homework #1 due, #2 out
Tue, Oct. 6 Regular languages and regular expressions
Reading: Sipser 1.3
Thu, Oct. 8 Nonregular languages and the pumping lemma
Reading: Sipser 1.4
Homework #2 due
Tue, Oct. 13 Context-free grammars
Reading: Sipser 2.1
Homework #3 out
Thu, Oct. 15 Midterm #1
Tue, Oct. 20 Pushdown automata
Reading: Sipser 2.2
Thu, Oct. 22 Non-context-free languages
Reading: Sipser 2.3
Tue, Oct. 27 Advanced topics in context-free languages
Reading: Sipser 2, exercises and problems
Homework #3 due, #4 out
Thu, Oct. 29 Context-free languages: catchup
Reading:
Tue, Nov. 3 Turing machines
Reading: Sipser 3.1 Homework #4 due
Thu, Nov. 5 Turing machine variants and the Church-Turing thesis
Reading: Sipser 3.2 and 3.3
Homework #5 out
Tue, Nov. 10 Midterm #2
Thu, Nov. 12 Decidable languages
Reading: Sipser 4.1
Tue, Nov. 17 Undecidable languages
Reading: Sipser 4.2
Homework #5 due, #6 out
Thu, Nov. 19 Reducibility
Reading: Sipser 5.1 and 5.3
Tue, Nov. 24 The recursion theorem
Reading: Sipser 6.1
Homework #6 due, #7 out
Thu, Nov. 26 Thanksgiving—No Class
Tue, Dec. 1 Introduction to Complexity
Reading: Sipser 7.x
Thu, Dec. 3 Catchup and advanced topics Reading:
Homework #7 due
Fri, Dec. 11 Final Exam

Navigation: CSE // CSE 105 // Syllabus