Skip to Main Content

CPSC511

Download as PDF

Introduction To Complexity Theory

Computer ScienceSC - Faculty of Science

Subject

CPSC - Computer Science

Description

Time and space complexity; the classes P, LOGSPACE, PSPACE and their nondeterministic counterparts; containments and separations between complexity classes; intractability and the theory of NP-completeness; complexity theories for probabilistic algorithms and for parallel algorithms.

Prerequisite(s): Computer Science 413.

Antirequisite(s): Credit for Computer Science 511 and 611 will not be allowed.

Course Attributes

Fee Rate Group(Domestic) - A, Fee Rate Group(International) -A, GFC Hours (3-0)

Courses may consist of a Lecture, Lab, Tutorial, and/or Seminar. Students will be required to register in each component that is required for the course as indicated in the schedule of classes. Practicums, internships or other experiential learning modalities are typically indicated as a Lab component.

Component

LEC

Units

3

Repeat for Credit

No

Subject code

CPSC
UCalgary Logo

Contact Us

Reach out to us if you have any questions about the new Calendar website or to provide feedback on any of the site navigation. For any questions regarding your program or for specific interpretations of regulations, please connect with an advisor for support.

Site Disclaimer

Please read the Important Notice and Disclaimer to understand your rights and responsibilities with regards to using the Academic Calendar.

Additional Information and Resources

The University of Calgary, located in the heart of Southern Alberta, both acknowledges and pays tribute to the traditional territories of the peoples of Treaty 7, which include the Blackfoot Confederacy (comprised of the Siksika, the Piikani, and the Kainai First Nations), the Tsuut’ina First Nation, and the Stoney Nakoda (including Chiniki, Bearspaw, and Goodstoney First Nations). The city of Calgary is also home to the Métis Nation within Alberta (including Nose Hill Métis District 5 and Elbow Métis District 6).

The University of Calgary is situated on land Northwest of where the Bow River meets the Elbow River, a site traditionally known as Moh’kins’tsis to the Blackfoot, Wîchîspa to the Stoney Nakoda, and Guts’ists’i to the Tsuut’ina. On this land and in this place we strive to learn together, walk together, and grow together “in a good way.”

Powered by Coursedog