Professor: Iluju Kiringa
(kiringa@site.uottawa.ca)
Office Hours: Thursday 3:00-4:00PM, in my office (SITE 5072)
Lectures: Thursday
4:00-7:00PM ; Brooks Residence (BRS) 204
Topics: Basic
computation models. Undecidability and related proof techniques. Basic computational resources
and their associated complexity classes (P, NP, Co-NP, PSPACE,
...). Relationships among resources and complexity
classes. Theory of class completeness (NP completeness, PSPACE completeness, ...) and related proof techniques. Inside P and Beyond NP. Randomized
computation.
Prerequisites: Required is a solid knowledge of design and analysis of algorithms as
well as undergraduate notions of computability.
Text book: M.J. Sipser, Introduction to the Theory of Computation,
2nd Edition, Thompson, 2006.
Supplemental reading: