Credits: 3 (3-0-0)
Prerequisites: COL202
Description
Regular Languages, Finite Automata, equivalence, minimization, Myhill-Nerode Theorem, introduction to non-determinism, Context free grammars, Pushdown automata, equivalence and applications. Turing machines, Recursive and Recursively enumerable sets, non- determinism, RAMs and equivalence, Universal Turing Machines, undecidability, Rice’s theorems for RE sets, Post machines, Basics of Recursive function theory. Equivalence, Church’s thesis, computational complexity, space and time complexity of Turing Machines, Relationships, Savage’s theorem, Complexity classes, Complete problems, NP-completeness, Cook-Levin theorem.
Prerequisite Tree
flowchart TD
COL352-185[COL352]
COL352-185 --> COL202-185[COL202]
classDef empty height:17px, fill:transparent, stroke:transparent;
classDef trueEmpty height:0px, width:0px;