Media Storage Type : 32 GB USB Stick
NPTEL Subject Matter Expert : Prof. Subrahmanyam Kalyanasundaram
NPTEL Co-ordinating Institute : IIT Madras
NPTEL Lecture Count : 69
NPTEL Course Size : 12 GB
NPTEL PDF Text Transcription : Available and Included
NPTEL Subtitle Transcription : Available and Included (SRT)
Lecture Titles:
Lecture 1 - An Introduction to The Theory of Computation
Lecture 2 - Notations and Terminology in Theory of Computation
Lecture 3 - An Introduction to Finite Automata and Regular Languages - Part 1
Lecture 4 - An Introduction to Finite Automata and Regular Languages - Part 2
Lecture 5 - Significance of Regular Languages and Regular Operations
Lecture 6 - Closure Properties of Regular Languages Under Union, Concatenation and Kleene Star Operation - Part 1
Lecture 7 - Closure Properties of Regular Languages Under Union, Concatenation and Kleene Star Operation - Part 2
Lecture 8 - An Introduction to Non-Deterministic Finite Automata (NFA)
Lecture 9 - Formal Definitions and Examples of Non-Deterministic Finite Automata (NFA)
Lecture 10 - Equivalence of NFA and DFA
Lecture 11 - Closure of Regular Languages Under Regular Operations (Using NFA)
Lecture 12 - Regular Expressions - Part 1
Lecture 13 - Regular Expressions - Part 2
Lecture 14 - Proving Equivalence of Regular Expression and DFA Through a GNFA
Lecture 15 - Pumping Lemma for Regular Languages - Part 1
Lecture 16 - Pumping Lemma for Regular Languages - Part 2
Lecture 17 - Distinguishability of Strings and Myhill-Nerode Theorem
Lecture 18 - Proving the Myhill-Nerode Theorem
Lecture 19 - An Introduction to Context-Free Languages - Part 1
Lecture 20 - An Introduction to Context-Free Languages - Part 2
Lecture 21 - Chomsky Normal Form
Lecture 22 - CYK Algorithm - Part 1
Lecture 23 - CYK Algorithm - Part 2 (Example)
Lecture 24 - Closure Properties of Context Free Languages
Lecture 25 - An Introduction to Push Down Automata
Lecture 26 - Normalizations in PDA and Intersection of Regular Language and CFL
Lecture 27 - Equivalence of Context Free Grammars and Push Down Automata - Part 1
Lecture 28 - Equivalence of Context Free Grammars and Push Down Automata - Part 2
Lecture 29 - Equivalence of Context Free Grammars and Push Down Automata - Part 3
Lecture 30 - Pumping Lemma for Context Free Languages
Lecture 31 - Examples of Pumping Lemma Usage for Context Free Languages
Lecture 32 - Formal Definition of a Turing Machine
Lecture 33 - Turing Recognizable and Decidable Languages and TM Examples
Lecture 34 - Multitape Turing Machine
Lecture 35 - Non-Deterministic Turing Machines
Lecture 36 - Equivalence of Deterministic and Nondeterministic TM
Lecture 37 - Church-Turing Thesis
Lecture 38 - Decidable Problems Concerning Regular Languages
Lecture 39 - Decidable Problems Concerning Context Free Languages
Lecture 40 - Countability of Sets
Lecture 41 - Proof of Existence of Undecidable Languages
Lecture 42 - Halting Problem
Lecture 43 - Co-Turing Recognizability
Lecture 44 - An Introduction to Mapping Reducibility
Lecture 45 - Examples of Proving Undecidability Using Reductions
Lecture 46 - Rice Theorem
Lecture 47 - Computation Histories
Lecture 48 - The Post Correspondence Problem
Lecture 49 - Checking Ambiguity in CFG is Undecidable
Lecture 50 - Time Complexity - Part 1
Lecture 51 - Time Complexity - Part 2
Lecture 52 - Non-Deterministic Polynomial Time - Part 1
Lecture 53 - Non-Deterministic Polynomial Time - Part 2
Lecture 54 - Verifiability and NP
Lecture 55 - Polynomial Time Reductions - Part 1
Lecture 56 - Polynomial Time Reductions - Part 2
Lecture 57 - NP-Completeness
Lecture 58 - Cook-Levin Theorem
Lecture 59 - Cook-Levin Theorem - Proof and Implications
Lecture 60 - CLIQUE and VERTEX-COVER is NP-Complete
Lecture 61 - HAM-PATH is NP-Complete
Lecture 62 - SUBSET-SUM is NP-Complete
Lecture 63 - Knapsack Problem
Lecture 64 - Integer Linear Program is NP-Complete
Lecture 65 - Space Complexity and its Complexity Classes
Lecture 66 - Logspace Reductions and NL-Completeness
Lecture 67 - Savitch's theorem
Lecture 68 - Results in Space Complexity
Lecture 69 - Summary and Concluding Remarks