CSE 105: Schedule and Readings


Date Topic and reading
Mon., Jan. 9 Introduction
Reading: Hammack 1
Wed., Jan. 11 Mathematical preliminaries
Reading: Hammack 2
Fri., Jan. 13 On proofs
Reading: Sipser 0
Exercise #1 collected
Mon., Jan. 16 Martin Luther King day: no class
Wed., Jan. 18 Deterministic finite automata
Reading: Sipser 1.1
Fri., Jan. 20 Nondeterministic finite automata
(HS traveling; guest lecturer: Steve Checkoway)
Reading: Sipser 1.2
Mon., Jan. 23 Regular languages and their closure properties
Reading: Hammack 4
Exercise #2 collected
Wed., Jan. 25 Regular expressions
Reading: Sipser 1.3
Fri., Jan. 27 Proving that a language is regular
Reading: none
Mon., Jan. 30 Nonregular languages and the pumping lemma
Reading: Sipser 1.4
Problem set #1 due
Wed., Feb. 1 Proving that a language is nonregular
(HS traveling; guest lecturer: Daniele Micciancio)
Reading: Hammack 5
Exercise #3 collected
Fri., Feb. 3 Pushdown automata
(HS traveling; guest lecturer: Steve Checkoway)
Reading: Sipser 2.2
Mon., Feb. 6 Context-free grammars
Reading: Sipser 2.1
Wed., Feb. 8 Equivalence of PDAs and CFGs
Reading: Hammack 6
Fri., Feb. 10 Non-context-free languages
Reading: Sipser 2.3
Problem set #2 due
Mon., Feb. 13 Turing machines
Reading: Sipser 3.1
Wed., Feb. 15 Turing machine variants and the Church-Turing thesis
Reading: Sipser 3.2 and 3.3
Exercise #4 collected
Fri., Feb. 17 Languages and input encoding
Reading: Hammack 7
Mon., Feb. 20 Washington's birthday (observed): no class
Wed., Feb. 22 Decidable languages
Reading: Sipser 4.1
Exercise #5 collected
Fri., Feb. 24 Diagonalization and the halting problem
Reading: Sipser 4.2
Mon., Feb. 27 Undecidable languages
Reading: Hammack 8
Problem set #3 due
Wed., Feb. 29 Reductions: I
Reading: Sipser 5.1
Fri., Mar. 2 Reductions: II
(HS traveling; guest lecturer: Daniele Micciancio)
Reading: none
Exercise #6 collected
Mon., Mar. 5 Reductions via computation histories
(HS traveling; guest lecturer: Steve Checkoway)
Reading: Hammack 9
Wed., Mar. 7 Mapping reductions
Reading: Sipser 5.3
Fri., Mar. 9 Computability catchup
Reading: Hammack 10
Exercise #7 collected
Mon., Mar. 12 Introduction to complexity: I
Reading: Sipser 7.1
Wed., Mar. 14 Introduction to complexity: II
Reading: Sipser 7.2 and 7.3
Problem set #4 due
Fri., Mar. 16 Introduction to complexity: III
Reading: Sipser 7.4
Mon., Mar. 19 Final Exam

Navigation: CSE // CSE 105 // Syllabus