Computer Science 511/611 — Introduction to Complexity Theory

Welcome to CPSC511/611!

CPSC 511 is a fourth-year undergraduate course in computational complexity theory. CPSC 611 is an introductory graduate course in this area which shares lectures with CPSC 511 but has somewhat different learning goals and assessment. These are available from the Department of Computer Science at the University of Calgary.

In Fall 2025 these will be an in-person courses. They will also be flipped courses: Students will be expected to complete a reading assignment (or, possibly, watch a lecture video) before attending each lecture. The lecture time will be used to briefly review the course reading, and to solve a problem that is related to the assigned reading and makes use of the material included in it.

The courses will each have a D2L course site which will be used for course communication and reporting of grades. All material, supplied to students for course work, will be made available on the D2L course site. The page that you are reading now (and other pages linked to it) includes a subset of theis material that can be accessed by people outside this course. These pages are certainly “under construction” at this point, and they describe the courses as they will be offered in Fall 2025.

Lecture Material Organized by Topic

  1. Introduction to Courses and Review of Turing Machines
  2. Deterministic Time
  3. Nondeterministic Time

Additional Course Information


University of Calgary Extension of Logo
Department of Computer Science

cpsc 511/611 computer science faculty of science u of c

cpsc 511/611 intro and review deterministic time nondeterministic time course administration recommended references