SCOMS3261-1: Computer Science Theory for Spring 2022

Days and Time

Tuesdays and Thursdays 1:10 PM-2:25 PM

Location

451 CSB

Allowed For:

  • Undergraduate
  • Masters
  • Professional
  • PhD

Prerequisites:

None

Notes:

None

Instructor:

Yannakakis, Mihalis

Description

Regular languages: deterministic and non-deterministic finite automata, regular expressions. Context-free languages: context-free grammars, push-down automata. Turing machines, the Chomsky hierarchy, and the Church-Turing thesis. Introduction to Complexity Theory and NP-Completeness.