CPSC 511: Introduction to Complexity Theory
About This Course
CPSC 511 is a fourth-year undergraduate course in computational complexity theory available from the Department of Computer Science at the University of Calgary.
In Winter 2024 this will be an in-person course. It will also be a flipped course: 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 course will 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 Winter 2024.
Course Outline
The course outline is now available, and this sentence is a link to it.
Lectures and Tutorials
- Introduction to the Course
- Deterministic Time
- Nondeterministic Time
- Space-Bounded Computation
- Circuit Complexity
- Randomized Computation
- Other Directions
Additional Course Material
- Recommended References
- More about Course Administration
- Information about Assignments
- Information about Tests
