CPSC 511 - Introduction to Complexity Theory
CPSC 611 - Complexity Theory
Course Summary
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
Textbook
Complexity Theory - Exploring the Limits of Efficient Algorithms, Ingo Wegener, Springer, 1st ed., 2005.
Requirements
- CPSC 413
- Interest in theoretical computer science.
Lectures
Time: Tuesdays and Thursdays, 9:30-10:45am.
Location: MS 527
Tutorials
Time: Wednesdays, 15:00-15:50
Location: ST 057
Forum
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.
Contact
See my homepage.
Office Hours
- Tuesdays and Thursdays, 11:00-11:45am (ICT 655), or
- by appointment.
Please approach me right after class if you want to meet me during my
regular office hours.