CSE 105: Schedule and Readings


Date Topic and reading
Mon., Oct. 1 Introduction; on proof
Reading: Hammack 1, Hammack 2, Sipser 0
Wed., Oct. 3 Deterministic finite automata
Reading: Sipser 1.1
Exercise #1 collected
Mon., Oct. 8 Nondeterministic finite automata
Reading: Sipser 1.2
Wed., Oct. 10 Regular languages and their closure properties
Reading: Hammack 4
Exercise #2 collected
Mon., Oct. 15 Regular expressions; proving that a language is regular
Reading: Sipser 1.3
Problem set #1 due
Wed., Oct. 17 Nonregular languages and the pumping lemma
Reading: Sipser 1.4
Mon., Oct. 22 Proving that a language is nonregular
Reading: Hammack 5
Exercise #3 collected
Wed., Oct. 24 Context-free grammars
Reading: Sipser 2.1
Mon., Oct. 29 Context-free languages and their closure properties
Reading: Hammack 6
Exercise #4 collected
Wed., Oct. 31 Non-context-free languages
Reading: Sipser 2.3
Mon., Nov. 5 Turing machines; languages and input encoding
Reading: Sipser 3.1
Problem set #2 due
Wed., Nov. 7 Turing machine variants and the Church-Turing thesis
Reading: Sipser 3.2 and 3.3
Mon., Nov. 12 Veterans’ day: no class
Reading: Hammack 7
Wed., Nov. 14 Decidable languages
Reading: Sipser 4.1
Exercise #5 collected
Mon., Nov. 19 Diagonalization and the halting problem
(HS traveling; guest lecturer TBD)
Reading: Sipser 4.2
Problem set #3 due
Wed., Nov. 21 Thanksgiving eve: no class
Mon., Nov. 26 Undecidable languages
Reading: Hammack 8
Wed., Nov. 28 Reductions
Reading: Sipser 5.1
Exercise #6 collected
Mon., Dec. 3 Mapping reductions
Reading: Sipser 5.3
Problem set #4 due
Wed., Dec. 5 Introduction to complexity
Reading: Hammack 9
Mon., Dec. 10 Final Exam

Navigation: CSE // CSE 105 // Syllabus