Computer Science 511/611 — (Introduction to) Complexity Theory

CPSC 511/611 — (Introduction to) Complexity Theory

About These Courses

CPSC 511 is a fourth-year undergraduate course in computational complexity theory available from the Department of Computer Science at the University of Calgary.

Course Outlines

The following outlines are the revised outlines approved in March 2020 and reflect changes to allow for social distancing during the Cornavirus pandemic.

CPSC 611 is a graduate course in the same area.

These courses currently share lectures but have significantly different assessment: While students in the undergraduate coursee are required to complete several tests, the graduate course has a significant project instead.

Lecture Topics

  1. Introduction to This Course
  2. Deterministic Computation
  3. Nondeterministic Computation
  4. Space-Bounded Computation
  5. Circuit Computations
  6. Randomization, Interaction and Approximation
  7. Structured Models of Computation
  8. Other Topics

Additional Course Material


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 to course deterministic computation nondeterministic computation space-bounded computation circuit computations randomzation, interaction and approximation structured models other topics assignments tests