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