CIS 511, Fall 2021

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:

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, Pspace, Pspace-complete problems.
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 (-).

Syllabus:

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

PART 1: Languages and Automata

The following topics will most likely be omitted.

PART II: Models of Computation, Undecidability, Basics of Recursive Function Theory

PART III: Computational Complexity


Back to Gallier Homepage

published by:

Jean Gallier