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.
This course may not be repeated for credit.
Notes
- Lectures may run concurrently with Computer Science 611[CPSC611].
Sections
| LEC 1 | TR 09:30 - 10:45
| | | | |
| TUT 1 | W 15:00 - 15:50
| | | | |
This course will be offered next in
Fall 2012.