COMP 3602: Introduction to the Theory of Computation

This course would be of interest to all computer science majors.

Prerequisites:  COMP 2002 or the former COMP 2711

Availability: This course is usually offered once per year, in Fall or Winter.

Course Objectives

This course addresses complexity and limitations of algorithmic problem solving relative to a variety of computational resources and machine models. It provides a formal introduction to theory of computation, presenting abstract machine models, the basics of computability theory and complexity theory.

Representative Workload
  • Assignments (6) 40%
  • In-class Exam 20%
  • Final Exam 40%
Representative Course Outline
  • Regular languages and finite automata (6 hours)
  • Context-free languages and pushdown automata (5 hours)
  • Turing machines, undecidability, many-one reductions (6 hours)
  • Complexity theory, polynomial-time reductions, P vs. NP (6 hours)
  • Other Topics (8 hours)
    • Recursion theorem
    • Space complexity
    • Circuit complexity
    • Parameterized complexity
    • Basic cryptography

Page last updated May 24th 2021