Theory of Computation (CSCI-UA 453)

This course takes a mathematical approach in studying topics in computer science, such as: regular languages and some of their representations (deterministic finite automata, non-deterministic finite automata, regular expressions); proof of non-regularity. Context free languages and pushdown automata; proofs that languages are not context free. Elements of computability theory. Brief introduction to NP-completeness.

Computer Science (Undergraduate)
4 credits – 15 Weeks

Sections (Spring 2022)


CSCI-UA 453-000 (9017)
01/24/2022 – 05/09/2022 Tue,Thu
9:00 AM – 10:00 AM (Morning)
at Washington Square
Instructed by Khot, Subhash