CIS 511, Spring 2010

Brief description:

The course provides an introduction to the theory of computation. The treatment is mathematical, but the point of view is that of Computer Science. Roughly speaking, the theory of computation consists of three overlapping subareas: (1) formal languages and automata; (2) Models of computation, computability, and basics of recursive function theory; (3) complexity theory.

This semester, we will put more emphasis on (2) and (3). In particular, for (3), we will cover the classes P and NP, NP-complete problems, co-NP, PS, NPS, RP, ZPP and the complexity of primality testing. In order to cover more material from (2) and (3), the order in which the material will be presented has been changed from previous years.

Applications of (1) to programming (and natural) language specification and parsing (top-down and bottom-up parsing) will be mentioned, whenever appropriate.

Students are expected to have some undergraduate knowledge of the theory of computation. Some material assumed to be known will either not be covered in class or reviewed quickly. This material is marked with a (-). Materiall not required for the WPE is marked with a (*).


Topics will include: ((*) means: if time permits)

PART 1: Languages and Automata

PART II: Models of Computation and Basics of Recursive Function Theory

PART III: Computational Complexity

PART IV: More Formal Language and Automata Theory

Back to Gallier Homepage

published by:

Jean Gallier