15-453 Formal Languages, Automata and Computation Fall 2005, TTH 12:00-1:20, HBH 1002 DATE LECTURE READING ASSIGNMENT Tue Aug 30 Overview (PPT) Chapters 0, 1.1   Thu Sep 1 Non-Determinism and the Pumping Lemma (PPT) Chapter 1.2 Homework 1 Tue Sep 6 Regular Expressions (PPT) Chapter 1.3   Thu Sep 8 Minimizing DFAs (PPT) Finish Chapter 1 Homework 2 Tue Sep 13 Context-Free Grammars and Push-Down Automata (PPT) Chapter 2   Thu Sep 15 Equivalence of PDAs and CFGs and The Chomsky Normal Form (PPT)   Homework 3 Tue Sep 20 Turing Machines (PPT) Chapter 3 Project Report 1 due Thu Sep 22 Review (PPT)     Tue Sep 27 Midterm Exam 1     Thu Sep 29 Undecidability (PPT) Chapter 4 Homework 4 Tue Oct 4 Undecidability II: Reductions (PPT) Chapter 5.1   Thu Oct 6 Post Correspondence Problem (PPT) Chapters 5.2 and 5.3 Homework 5 Tue Oct 11 The Arithmetic Hierarchy (PPT)     Thu Oct 13 The Recursion Theorem; Rice's Theorem; The Fixed-Point Theorem (PPT) Chapter 6.1 Homework 6 Tue Oct 18 Time Complexity and Polynomial Time (PPT) Chapters 7.1 and 7.2   Thu Oct 20 Non-Deterministic Turing Machines and NP (PPT) Chapter 7.3 Homework 7 Tue Oct 25 NP-Completeness: The Cook-Levin Theorem (PPT) Chapters 7.4 and 7.5   Thu Oct 27 Review (PPT)     Tue Nov 1 Midterm Exam 2     Thu Nov 3 NP-Completeness II (PPT)   Homework 8 Tue Nov 8 Space Complexity: Savitch's Theorem and PSPACE (PPT) Chapters 8.1 and 8.2   Thu Nov 10 PSPACE-Completeness (PPT) Chapter 8.3 Homework 9 Tue Nov 15 co-Classes and Relative Complexity (PPT)     Thu Nov 17 The Polynomial Hierarchy     Tue Nov 22 Randomized Complexity: BPP, RP, etc. (PPT) Chapter 10.2   Thu Nov 24 No Class, THANKSGIVING!     Tue Nov 29 Computing Over the Reals     Thu Dec 1 Project Presentations I     Tue Dec 6 Project Presentations II     Thu Dec 8 FINAL EXAM     © 2005 Carnegie Mellon University, all rights reserved.