Miser Project Readings

R010800: Sketching Computation Theory

[Sipser1997]

Sipser, Michael. Introduction to the Theory of Computation. PWS Publishing (Boston, MA: 1997). ISBN 0-534-94728-X.

Michael Sipser is a member of the MIT Theory of Computation Group. His book is being used as the basis for an on-line study program of the Learn-CS-Theory discussion group. The syllabus, below, follows the chapter structure, week by week.

Last updated 2002-03-17-12:29 -0800 (pst)

Week	Topic	Status
2001-08-06	0. Introduction 0.1 Automata, Computability, and Complexity 0.2 Mathematical Notions and Terminology 0.3 Definitions, Theorems, and Proofs 0.4 Types of Proof Exercises and Problems
2001-08-13	1. Regular Languages 1.1 Finite Automata
2001-08-20	1.2 Nondeterminism
2001-08-27	1.3 Regular Expressions
2001-09-03	1.4 Nonregular Languages Exercises and Problems
2001-09-10	2. Context-Free Languages 2.1 Context-Free Grammars
2001-09-17	2.2 Pushdown Automata
2001-09-25	2.3 Non-context-free Languages Exercises and Problems
2001-10-01	3. The Church-Turing Thesis 3.1 Turing Machines
2001-10-08	3.2 Variants of Turing Machines
2001-10-15	3.3 The Definition of Algorithm Exercises and Problems
2001-10-22	4. Decidability 4.1 Decidable Languages
2001-10-29	4.2 The Halting Problem Exercises and Problems
2001-11-05	5. Reducibility 5.1 Undecidable Problems from Language Theory
2001-11-12	5.2 A Simple Undecidable Problem
2001-11-19	5.3 Mapping Reducibility Exercises and Problems
2001-11-26	6. Advanced Topics in Computability Theory 6.1 The Recursion Theorem
2001-12-03	6.2 Decidability of Logical Theories 6.3 Turing Reducibility
2001-12-10	6.4 A Definition of Information Exercises and Problems
2001-12-17	7. Time Complexity 7.1 Measuring Complexity
2001-12-24	7.2 The Class P
2001-12-31	7.3 The Class NP
2002-01-07	7.4 NP-Completeness
2002-01-14	7.5 Additional NP-Complete Problems Exercises and Problems
2002-01-21	8. Space Complexity 8.1 Savitch's Theorem 8.2 The Class PSPACE
2002-01-28	8.3 PSPACE-Completeness
2002-02-04	8.4 The Classes L and NL 8.5 NL-Completeness 8.6 NL Equals coNL Exercises and Problems
2002-02-11	9. Intractability 9.1 Hierarchy Theorems
2002-02-18	9.2 Relativization
2002-02-25	9.3 Circuit Complexity Exercises and Problems
2002-03-04	10. Advanced Topics in Complexity Theory 10.1 Approximation Algorithms 10.2 Probabilistic Algorithms
2002-03-11	10.3 Alternation
2002-03-18	10.4 Interactive Proof Systems
2002-03-25	10.5 Parallel Computation
2002-04-01	10.6 Cryptography Exercises and Problems

created 2001-08-07-22:07 -0700 (pdt) by orcmid
$$Author: Orcmid $
$$Date: 02-10-13 21:38 $
$$Revision: 7 $

Home