Course Schedule

This table will be updated as the class progresses. All readings are in the text book unless otherwise noted.

Date Lecture Readings Homework
9/20 Course Introduction, Finite Automaton: definition, examples 0.1 - 0.4, 1.1  
9/25 Regular operations, nondeterminism 1.2  
9/27 NFA's, regular ops 1.3  
10/2 Reg. exp.'s 1.3 HW 1
10/4 Review session: Sample problems we will do in class 1.1-1.3  
10/9 Non-Regular Languages, Pumping Lemma 1.4 HW 1 Answer Sheet
10/11 Pumping Lemma Proof, size of NFA's, DFA's 1.4  
10/16 Quiz 1, Mandeville Aud. Intro to CFG's 2.1  
10/18 Context-free grammars, parse trees, ambiguity 2.1  
10/23 Chomsky Normal Form, Pushdown automata 2.2  
10/25 More PDA 2.2 HW 2
10/30 Pumping Lemma, Non-CFL (notes last lecture) 2.3 HW 2 Answer Sheet
11/1 Intro to Turing Machines 3.1  
11/6 Quiz 2, Mandeville Aud. Variants of TM 3.2  
11/8 More Variants, Equivalence 3.2, 3.3  
11/13 Decidable Problems 4.1  
11/15 Undecidability, The Halting Problem 4.2 HW 3
11/20 Reducibility 5.1, 5.3 HW 3 Answer Sheet
11/22 Thanksgiving Holiday    
11/27 Quiz 3, Price Center Th., Complexity 7.1  
11/29 Last Lecture: P and NP 7  
M 12/3 Final Exam, 3 - 6 pm, Price Center Th.