WCOMS3261-1: Computer Science Theory for Spring 2018

Days and Time

Mondays and Wednesdays 10:10 AM-11:25 AM

Location

RTBA BTBA

Allowed For:

  • Undergraduate

Prerequisites:

COMS W3137 and W3203.

Notes:

None

Instructor:

Malkin, Tal G

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.