Formal methods of computation based on machines, grammars and languages: finite automata vs. regular languages; pushdown automata vs. context-free grammars; Turing machines vs. unrestricted grammars. Models of computation equivalent to Turing machines and Church's Thesis. Computability and Uncomputability. Introduction to Theory of Computational Complexity with emphasis on the Theory of NP-completeness.

 

Prerequisites:

CS 111: Discrete Structures in Computer Science and Computation

MAS 004: Introductory Mathematics I