Week 1: Introduction to the course, DFAs, Regular Languages, Regular operations, Closure under union
Week 2: NFAs, Equivalence of DFAs and NFAs, Closure properties, regular expressions, Equivalence of Regular expressions and DFAs.
Week 3: Pumping Lemma for regular languages, Myhill-Nerode Theorem, Context-free grammars
Week 4: Chomsky Normal Form, CYK Algorithm, Closure properties of CFLs, Pushdown Automata
Week 5: Equivalence of PDAs and CFGs, Pumping Lemma for CFLs, Introduction to Turing machines
Week 6: Decidable (recursive) languages, Turing-Recognizable (recursively enumerable) languages, Multi-tape TMs, NTMs, Equivalence, Church Turing thesis
Week 7: Decidable languages from regular and context-free languages, Countable and uncountable sets, Halting Problem and undecidability.
Week 8: Reductions. Decidable and undecidable languages using reductions. Rice’s theorem. Computation Histories.
Week 9: Post Correspondence Problem (PCP) is undecidable, Introduction to Complexity Theory. Asymptotic notation, Classes P and NP.
Week 10: Verifier model for NP, Polynomial Time reductions, NP Completeness, Cook-Levin Theorem
Week 11: NP Complete problems like Vertex Cover, Hamiltonian Path, Subset Sum, ILP
Week 12: Space Complexity, Relation with time bounded complexity classes, introduction to classes like L, NL, PSPACE and overview of results in space complexity
DOWNLOAD APP
FOLLOW US