| W | L | Date | Topic | Reading | Comments |
|---|---|---|---|---|---|
| 1 | 1 | 2008-01-07 | Course agenda, policies, introduction to sets | Chapter 1 | |
| 2 | 2008-01-09 | Introduction to finite automata | Chapter 2, up to 2.2 | Assignment 1 out | |
| 2 | 3 | 2008-01-14 | DFA examples and introduction to NFAs | Chapter 2, up to 2.2 | |
| 4 | 2008-01-16 | NFAs: equivalence to DFAs | Chapter 2, up to 2.3 | Assignment 2 out | |
| 3 | 2008-01-21 | Martin Luther King Day (no lecture) | |||
| 5 | 2008-01-23 | Applications of FA, ε-NFAs and their equivalence to DFAs | Chapter 2 | Assignment 3 out | |
| A | 2008-01-23 | Recitation (Lindley Hall 101, 7:00 PM) | |||
| 4 | 6 | 2008-01-28 | Introduction to regular expressions | Chapter 3 (up to Section 3.1) | |
| 7 | 2008-01-30 | Equivalence of REs and DFAs | Chapter 3 | Assignment 4 out | |
| 5 | 8 | 2008-02-04 | Converting a DFA to RE | Chapter 3 (up to Section 3.4.5) | |
| 9 | 2008-02-06 | Pumping Lemma for regular languages, closure properties | Chapter 4 (up to Section 4.2.2) | Assignment 5 out | |
| B | 2008-02-06 | Recitation (Lindley Hall 101, 7:00 PM) | |||
| 6 | 10 | 2008-02-11 | Homomorphism and inverse homomorphism | Chapter 4 (up to Section 4.2) | |
| 2008-02-13 | Mid-term I (Chapter 1 through Section 4.2) | ||||
| 7 | 11 | 2008-02-18 | DFA minimization | Section 4.4 | |
| 12 | 2008-02-20 | Introduction to CFGs | Section 5.1 | Assignment 6 out | |
| 8 | 13 | 2008-02-25 | Parse trees, recursive inferences to parse trees | Section 5.2 (up to 5.2.4) | |
| 14 | 2008-02-27 | Re-cap of basic concepts: induction | |||
| 9 | 15 | 2008-03-03 | Recap of basic concepts: graphs, algorithms | ||
| 16 | 2008-03-05 | Wrap-up of CFLs: ambiguity, pumping lemma | Sections 5.2, 5.4, 7.2; (suggested: 7.4.4) | Assignment 7 out | |
| 10 | 17 | 2008-03-17 | Undecidability | Section 8.1 | |
| 18 | 2008-03-19 | Introduction to Turing Machine | Section 8.2 | Assignment 8 out | |
| 11 | 19 | 2008-03-24 | Turing machine techniques, equivalence of TM and computers | Sections 8.3, 8.6 | |
| 20 | 2008-03-26 | Extensions to Turing machine | Section 8.4 | Assignment 9 out | |
| 12 | 21 | 2008-03-31 | Restricted models of computation | Section 8.5 | |
| 2008-04-02 | Mid-term II (Section 4.4 through Chapter 8—only the covered portions) | ||||
| 13 | 22 | 2008-04-07 | Ld as a non-RE language, Lu as a non-recursive RE language | Sections 9.1, 9.2 | |
| 23 | 2008-04-09 | Reductions, Le and Lne, relations between language classes, Rice's theorem | Section 9.3 | Assignment 10 out | |
| 14 | 24 | 2008-04-14 | Intractable problems, NP-completeness | Sections 10.1, 10.2 | |
| 25 | 2008-04-16 | P vs NP | Sections 10.1, 10.2 | Assignment 11 out | |
| 15 | 26 | 2008-04-21 | Proving NP-completeness | Chapter 10 (except Post's Correspondence Problem) | |
| 27 | 2008-04-23 | Complexity classes | Lecture Notes | ||
Unless noted otherwise, chapter and section numbers refer to the chapters and sections from the textbook.