The theory of computations course provides the fundamental complexity theory and models useful for solving computational problems. Topics include basic computational theory, computational models including nondeterministic alternating and probabilistic machines, Boolean circuits, complexity classes related to models of computing including NP, polynomial hierarchy, BPP among others, complete problems, interactive proof systems and probabilistic proofs, randomized algorithms, structural complexity and complexity hierarchy.