BLG 557E - Theory of Computation

Course Objectives

1. To provide a general overview of computation and complexity issues.
2. To discuss basic principles of computability.
3. To discuss basic principles of complexity.
4. To ensure that students have the necessary research skills to apply basic computability analysis using fundamental computation models.

Course Description

Overview of types of formal languages and automata and recursively enumerable languages, computation models and computability, decidability and reducibility, introduction of advanced topics in theory of computation, space and time complexity, intractability, introduction of advanced topics in theory of complexity.