| W | L | Date | Topic | Reading | Comments |
|---|---|---|---|---|---|
| 1 | 1 | 2007-01-08 | Course agenda, policies, introduction to sets | Chapter 1 | |
| 2 | 2007-01-10 | Introduction to finite automata | Chapter 2 | Assignment 1 out | |
| 2 | 2007-01-15 | Martin Luther King Day—no class | |||
| 3 | 2007-01-17 | DFAs and NFAs | Chapter 2 | Assignment 2 out | |
| 3 | 4 | 2007-01-22 | Proving correctness, converting NFAs to DFAs by subset construction | Chapter 2 through Section 2.4 | |
| 5 | 2007-01-24 | ε-transitions, introduction to regular expressions | Sections 2.5, 3.1 | Assignment 3 out | |
| 4 | 6 | 2007-01-29 | Examples of regular expressions, regular expressions to ε-NFAs | Sections 3.1 through 3.2.1 | |
| 7 | 2007-01-31 | DFAs to regular expressions, algebraic laws of regular expressions | Chapter 3 | Assignment 4 out | |
| 5 | 8 | 2007-02-05 | Pumping Lemma for regular languages | Section 4.1 | |
| 9 | 2007-02-07 | Closure properties of regular languages | Section 4.2 | Assignment 5 out | |
| 6 | 10 | 2007-02-12 | Decision properties of regular languages, DFA minimization | Sections 4.3, 4.4 | |
| 2007-02-12 | Review session (7:00 PM, Lindley 101) | ||||
| 11 | 2007-02-14 | Class canceled, campus closed until noon due to snow emergency Midterm 1 postponed until Feb 19th (Mon) | |||
| 7 | 2007-02-19 | Midterm Exam 1 | |||
| 12 | 2007-02-21 | Introduction to context-free languages and context-free grammars | Section 5.1 | Assignment 6 out | |
| 8 | 13 | 2007-02-26 | Proofs involving CFGs, parse trees | Chapter 5 up to Section 5.2.2 | |
| 14 | 2007-02-28 | Equivalence of parse trees, derivations, and recursive inference; application to parsing | Sections 5.2, 5.3 | Assignment 7 out | |
| 9 | 15 | 2007-03-05 | Ambiguity in CFGs and CFLs, introduction to Pushdown Automata | Sections 5.3, 5.4, 6.1 | |
| 16 | 2007-03-07 | NPDAs and DPDAs, Chomsky Normal Form for CFGs | Sections 6.2 (up to 6.2.2), 6.4, 7.1 (read 7.1.4 to solve Problem 4(b) in Assignment 8) | Assignment 8 out | |
| 10 | 2007-03-12 | Spring break | |||
| 2007-03-14 | Spring break | ||||
| 11 | 17 | 2007-03-19 | Converting a CFG to CNF | Section 7.1 | |
| 18 | 2007-03-21 | Pumping lemma for CFLs, closure properties | Sections 7.2, 7.3 (except 7.3.5), 7.4.4 | Assignment 9 out | |
| 2007-03-23 | Review session (12:30 PM, Lindley 101) | ||||
| 12 | 19 | 2007-03-26 | Introduction to undecidability | Section 8.1 | |
| 2007-03-28 | Midterm Exam 2 | ||||
| 13 | 20 | 2007-04-02 | Introduction to Turing machines | Section 8.2 | |
| 21 | 2007-04-04 | TM programming tricks, equivalences of extensions to TM to standard TM | Sections 8.3, 8.4 | Assignment 10 out | |
| 14 | 22 | 2007-04-09 | Multi-stack and counter machines, Ld as a non-RE language | Sections 8.5, (optionally 8.6), 9.1, 9.2 (up to 9.2.2) | |
| 23 | 2007-04-11 | Lu as an RE-but-not-recursive language, reductions | Sections 9.2, 9.3 (up to 9.3.2) | Assignment 11 out | |
| 15 | 24 | 2007-04-16 | PCP and its application to the CFG ambiguity problem, Rice's theorem, introduction to classes P and NP | Sections 9.3, 9.4.1, 9.5.2 | |
| 25 | 2007-04-18 | Classes P and NP, 3SAT, independent set | Sections 10.1, 10.2.1, 10.2.2, 10.3 (except 10.3.3), 10.4 (up to 10.4.2) | Assignment 12 out | |
| 16 | 26 | 2007-04-23 | Some NP-complete problems | Section 10.4.3, Exercises 10.4.1, 10.4.2 | |
| 27 | 2007-04-25 | Conclusion of discussion on NP-completeness, review, course evaluation | |||
| 2007-05-02 | Final Exam (10:15 AM-12:15 PM) | ||||
Unless noted otherwise, chapter and section numbers refer to the chapters and sections from the textbook.
B401, Arun Chauhan, Department of Computer Science, Indiana University