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