CPSC 511 - Introduction to Complexity Theory
CPSC 611 - Complexity Theory
The area of complexity theory deals with determining the
amounts of resources (e.g., time orspace) that are needed to solve a problem, and classifying
computational problems by their difficulty. Understanding the
computational complexity of problems and the limits of efficient
algorithms, prevents computer scientists from searching for
non-existing efficient algorithms. This course will explore
fundamental concepts of complexity theory, such as
- time complexity,
- space complexity,
- the polynomial hierarchy and alternations,
- alternative computation models
Complexity Theory - Exploring the Limits of Efficient Algorithms, Ingo Wegener, Springer, 1st ed., 2005.
- CPSC 413
- Interest in theoretical computer science.
Time: Tuesdays and Thursdays, 9:30-10:45am.
Location: MS 527
Time: Wednesdays, 15:00-15:50
Location: ST 057
News and handouts will be posted to the course forum.
If you have questions that may be interesting to all students, please ask them in the "discussion" section of the forum.
See my homepage.
Please approach me right after class if you want to meet me during my
regular office hours.
- Tuesdays and Thursdays, 11:00-11:45am (ICT 655), or
- by appointment.