Professor: Iluju Kiringa (kiringa@site.uottawa.ca)
Office Hours: Wednesdays 11:30-12:30AM
(Increased on rush days) in my office (SITE 5072)
Lectures: Wednesday 1:00-4:00PM ; CBY E016
Topics: Basic computation modelss.
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. Randomized computation. Inside P and Beyond NP.
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: