This Schedule is tentative, but the topics we’ll cover should not deviate too much from it.


DateLectureReadingAssignment
Tue Jan 13Overview
Deterministic Finite Automata and Regular Languages		Chapters 0, 1.1
Thu Jan 15Non-determinism and Regular OperationsChapter 1.2HW1 out
Tue Jan 20Regular Expressions and the Pumping Lemma for Regular LanguagesChapter 1.3, 1.4Quiz 1 (preview)
Thu Jan 22Minimizing DFAsFinish Chapter 1HW 1 due
HW 2 out
Tue Jan 27Push-Down Automata and Context-Free Grammars; Pumping Lemma for CFLsChapter 2.1, 2.2, 2.3Quiz 2 (preview)
Thu Jan 29Equivalence of PDAs and CFGsHW 2 due
HW 3 out
Checkpoint 1 out
Tue Feb 3Chomsky Normal Form, Turing MachinesChapter 2, Chapter 3
Thu Feb 5UndecidabilityChapter 3, Chapter 4Project Report 1 due
Checkpoint 1 due Friday
Tue Feb 10ReviewHW 3 due
Thu Feb 12Midterm 1
Tue Feb 17Undecidability II: ReductionsChapter 5.1
Thu Feb 19More Mapping ReducibilitiesChapter 5.3
Tue Feb 24Post Correspondence ProblemChapter 5.2Checkpoint 3 due
Thu Feb 26Rice’s Theorem; The Recursion Theorem; The Fixed-Point TheoremChapter 6
Tue Mar 3Oracle Turing Machines and Turing Reducibility Chapter 6HW 4 due
Thu Mar 5The Arithmetic HierarchyChapter 6
Tue Mar 10Spring break
Thu Mar 12Spring break
Tue Mar 17Kolmogorov-Chaitin ComplexityChapter 6Checkpoint 6 out
HW 6 out
Thu Mar 19Time Complexity and Polynomial Time; Non-Deterministic Turning Machines and NPChapter 7
Tue Mar 24NP-Completeness: The Cook-Levin TheoremChapter 7Project Report 2 due
Homework 7 out
Checkpoint 7 out
Thu Mar 26NP-Completeness: The Cook-Levin TheoremChapter 7
Tue Mar 31NP-Completeness: KarpChapter 7
Thu Apr 2Space Complexity: Savitch's Theorem and PSPACE-CompletenessChapter 8Homework 8
Tue Apr 7Review
Thu Apr 9Midterm 2
Tue Apr 14Space ComplexityChapter 8
Thu Apr 16Carnival
Tue Apr 2110 SZ random reduction
Thu Apr 23Project presentationsHW 9
Tue Apr 28Project presentations
Thu Apr 30Review 1
Review 2
Review 3		Final project report due
Final date TBD
Copyright 2014 Carnegie Mellon University, all rights reserved.