The Miser Project

Miser Project Readings
Sketching Computation Theory

miser>readings>

r010800>
0.01 2017-08-29 16:40


This is a syllabus that follows the content of 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.

I didn't follow this beyond the first week's introductory material.  I am now waiting for the next convenient offering of Ullman's Automatia Theory course on Coursera, instead.  I have observations in my note on the first week's material.  I will nail some of this down as part of the demonstration of oMiser universality and generalization.  I'll do that in appropriate places.  This page will remain for reference purposes.  I don't foresee developing it further in this form, although some of the later topics are worth visiting further.

-- Dennis E. Hamilton
Seattle, Washington
2014-05-03

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

 
0.01 2014-05-03-09:28 Repaved Version
The page is updated to conform to current styles and formats.  The material is preserved as a historical matter and to avoid breaking any links that may have existed to it.  However, the capitalizations in URLs have changed, and that may break older versions.
0.00 2000-08-09-08:00 Develop Initial Notes (orcmid)
Extract notes on how this material is applicable to the Miser Project

Construction Structure (Hard Hat Area)

You are navigating the Miser Project.

created 2001-08-07-22:07 -0700 (pdt) by orcmid
$$Date: 17-08-29 16:40 $
$$Revision: 16 $