Theory of Computation

This course covers of the basics of automata and language theory, computation theory, and complexity theory. The first part of the course is about automata and regular languages, context free grammars, Church’s thesis, decidability, and reducibility. Topics in the second part of the course include: time complexity and NP-completeness, space complexity, polynomial-space and log-space computations, circuit complexity, probabilistic computations and complexity classes, approximation algorithms, and selected topics as time permits.