Professor: Iluju Kiringa (email@example.com)
Office Hours: Tuesday 13:00-14:00PM, in my office (SITE 5072)
Lectures: Tuesday / Thursday) 16:00-17:30 / 14:30-16:00; TBT 319 / SMD 227
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.