
15453 Formal Languages, Automata, and Computation

Date  Lecture  Reading  Homework Due  



Mon  Jan  17  Martin L. King Day  
Wed  Jan  19  Overview  Ch. 0  
Fri  Jan  21  Finite Automata  Ch. 1, pp. 3154  


Mon  Jan  24  Applications of Finite State Machines  Handout 3  
Wed  Jan  26  Model Checking  Handout 4  
Fri  Jan  28  NonDeterministic Finite Automata  Ch. 1, pp. 5358, Handout 5 
Assignment 1  


Mon  Jan  31  Regular Expressions  Ch. 1, pp. 6476  
Wed  Feb  2  Nonregular Languages  Ch. 1.4, pp. 7783  
Fri  Feb  4  ContextFree Grammars  Ch. 2.1, pp. 91101  Assignment 2  


Mon  Feb  7  Regular Grammars  Handout 9  
Wed  Feb  9  Pushdown Automata  Ch. 2.2, pp. 101110  
Fri  Feb  11  PDAs and ContextFree Grammars  Ch. 2.2, pp. 111114  Assignment 3  


Mon  Feb  14  NonContextFree Languages  Ch. 2.3, pp. 115119  
Wed  Feb  16  Review  Ch. 1 & 2  
Fri  Feb  18  Midterm I  Practice Midterm I  Assignment 4  


Mon  Feb  21  Turing Machines  Ch. 3.1, pp. 125135  
Wed  Feb  23  Variants of Turing Machines  Ch. 3.2, pp. 134138  
Fri  Feb  25  NonDeterministic Turing Machines  Ch. 3.2, pp. 138140  


Mon  Feb  28  Decision Procedures  Ch. 4.1, pp. 151158  
Wed  Mar  1  The Halting Problem  Ch. 4.2, pp. 159168  
Fri  Mar  3  Reductions  Ch. 5.3, pp. 189194, Slides in HTML and PostScript 
Assignment 5  


Mon  Mar  6  Midsemester Holiday  
Wed  Mar  8  Some Undecidable Problems  Ch. 5.1, pp. 171176  
Fri  Mar  10  Computation Histories  Ch. 5.1, pp. 176182  Assignment 6  


Mon  Mar  13  Mapping Reductions  Ch. 5.3, pp. 189194  
Wed  Mar  15  Post Correspondence Problem  Ch. 5.2, pp. 183189  
Fri  Mar  17  Tiling  not in book  Assignment 7  


Mon  Mar  20  The LambdaCalculus  not in book  
Wed  Mar  22  Review  Ch. 35, pp. 125196  
Fri  Mar  24  Midterm II  Practice Midterm II  


Mar 2731 Spring Break  


Mon  Apr  3  Time Complexity  Ch. 7.1, pp. 225234  
Wed  Apr  5  Polynomial Time  Ch. 7.2, pp. 232236  
Fri  Apr  7  Some Problems in P  Ch. 7.2, pp. 236241  


Mon  Apr  10  Verifiers  Ch. 7.3, pp. 241244  
Wed  Apr  12  The Class NP  Ch. 7.3, pp. 244248  Assignment 8  
Fri  Apr  14  Spring Carnival  


Mon  Apr  17  Polynomial Time Reductions  Ch. 7.4, pp. 248253  
Wed  Apr  19  NPCompleteness  Ch. 7.4, pp. 253260  
Fri  Apr  21  The Importance of SAT  Lecture notes; Addendum  Assignment 9  


Mon  Apr  24  The Vertex Cover Problem  Ch. 7.5, pp. 260262  
Wed  Apr  26  The Hamiltonian Path Problem  Ch. 7.5, pp. 262268  
Fri  Apr  28  Space Complexity  Ch. 8.18.2, pp. 277282  Assignment 10  


Mon  May  1  PSPACECompleteness  Ch 8.3, pp. 283288  
Wed  May  3  Review  Ch. 7.18.3, pp. 225288  
Fri  May  5  Reading Day (no class)  


Fri  May  12  Final, 8:3011:30, WeH 7500  

[ Home  Schedule  Assignments  Handouts  Overview ]
fp@cs
Frank Pfenning