Statement of Course Outcomes

Course Number: CS 601

Course Name: Computational Complexity

Course Coordinator: John Oliensis

Graduate or Undergraduate Equivalent:

Catalog Description: Analysis of algorithms: resource-bounded computation and time and space complexity. Various models of computation will be studied. Complexity classes and reducibilities, hardness, and completeness. Randomized algorithms and approximation algorithms. Prerequisite: CS 600.

Course Outcomes

Each course outcome is followed in parentheses by the Program Outcome to which it relates.

- be able to use big-O notation to describe and compare the running time of algorithms [core:problem-solving]

- be able to define common complexity classes, including P, NP, coNP, and PSPACE [core:problem-solving]

- know what it means for a problem to be NP-complete [core:problem-solving]

- be able to demonstrate that certain problems belong to certain complexity classes [core:problem-solving]

- be able to prove NP-complete problems are NP-complete [core:problem-solving]