Syllabus for End Semester cs222

1. Push-Down Automata and Context Free Languages: Designing CFGs, Ambiguity, Closure properties
2. Computability: Turing Machines, Church-Turing Thesis, Variants of Turing machines, non-determinism, enumerators, Decidability, Halting problem, Reducibility, Undecidability, Godel’s incompleteness theorem
3. Computational Complexity: The classes P and NP, Boolean circuits, NP Completeness (example problems: SAT)