Courses with significant overlap with this course:

Semester of last offering:

Date of approval: dd-mmm-yyyy

Prerequisites: 

Course Contents

Regular languages, Deterministic and nondeterministic nite automata, Closure properties, Languages that are and are not regular, State minimization in deterministic nite automata. Context free languages, Closure properties, Parse trees, Languages that are and are not context free, Pushdown automata. Turing machines, Turing computability, Church Turing thesis, Halting problem, Some un decidable problems. Computational complexity, Classes P and NP, NP completeness, Examples of NP complete problems.