CSE 105: Automata and Computability Theory


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

Navigation: CSE // CSE 105 // Syllabus