Learn · NPTEL

Course10610624270 lectures

Theory of Computation

Prof. Subrahmanyam Kalyanasundaram · IIT Hyderabad

Start with lecture 1 At NPTEL

Lectures

week-01

  1. An Introduction to The Theory of Computation Video
  2. Notations and Terminology in Theory of Computation Video
  3. An Introduction to Finite Automata and Regular Languages - Part 01 Video
  4. An Introduction to Finite Automata and Regular Languages - Part 02 Video
  5. Significance of Regular Languages and Regular Operations Video
  6. Closure Properties of Regular Languages Under Union, Concatenation and Kleene Star Operation-Part 01 Video
  7. Closure Properties of Regular Languages Under Union, Concatenation and Kleene Star Operation-Part 02 Video

week-02

  1. An Introduction to Non-Deterministic Finite Automata (NFA) Video
  2. Formal Definitions and Examples of Non-Deterministic Finite Automata(NFA) Video
  3. Equivalence of NFA and DFA Video
  4. Closure of Regular Languages Under Regular Operations(Using NFA) Video
  5. Regular Expressions - Part 01 Video
  6. Regular Expressions - Part 02 Video
  7. Proving Equivalence of Regular Expression and DFA Through a GNFA Video

week-03

  1. Pumping Lemma for Regular Languages - Part 01 Video
  2. Pumping Lemma for Regular Languages - Part 02 Video
  3. Distinguishability of Strings and Myhill-Nerode Theorem Video
  4. Proving the Myhill-Nerode Theorem Video
  5. An Introduction to Context-Free Languages - Part 01 Video
  6. An Introduction to Context-Free Languages - Part 02 Video

week-04

  1. Chomsky Normal Form Video
  2. CYK Algorithm - Part 1 Video
  3. CYK Algorithm - Part 2 (Example) Video
  4. Closure Properties of Context Free Languages Video
  5. An Introduction to Push Down Automata Video
  6. Normalizations in PDA and Intersection of Regular Language & CFL Video

week-05

  1. Equivalence of Context Free Grammars and Push Down Automata - Part 01 Video
  2. Equivalence of Context Free Grammars and Push Down Automata - Part 02 Video
  3. Equivalence of Context Free Grammars and Push Down Automata - Part 03 Video
  4. Pumping Lemma for Context Free Languages Video
  5. Examples of Pumping Lemma Usage for Context Free Languages Video
  6. Formal Definition of a Turing Machine Video

week-06

  1. Turing Recognizable & Decidable Languages and TM Examples Video
  2. Multitape Turing Machine Video
  3. Non-Deterministic Turing Machines Video
  4. Equivalence of Deterministic and Nondeterministic TM Video
  5. Church-Turing Thesis Video

week-07

  1. Decidable Problems Concerning Regular Languages Video
  2. Decidable Problems Concerning Context Free Languages Video
  3. Countability of Sets Video
  4. Proof of Existence of Undecidable Languages Video
  5. Halting Problem Video
  6. Co-Turing Recognizability Video

week-08

  1. An Introduction to Mapping Reducibility Video
  2. Examples of Proving Undecidability Using Reductions Video
  3. Rice Theorem Video
  4. Computation Histories Video

week-09

  1. The Post Correspondence Problem Video
  2. Checking Ambiguity in CFG is Undecidable Video
  3. Time Complexity - Part 1 Video
  4. Time Complexity - Part 2 Video
  5. Non-Deterministic Polynomial Time - Part 1 Video
  6. Non-Deterministic Polynomial Time - Part 2 Video

week-10

  1. Verifiability and NP Video
  2. Polynomial Time Reductions - Part 1 Video
  3. Polynomial Time Reductions - Part 2 Video
  4. NP-Completeness Video
  5. Cook-Levin Theorem Video
  6. Cook-Levin Theorem - Proof and Implications Video

week-11

  1. CLIQUE and VERTEX-COVER is NP-Complete Video
  2. HAM-PATH is NP-Complete Video
  3. SUBSET-SUM is NP-Complete Video
  4. Knapsack Problem Video
  5. Integer Linear Program is NP-Complete Video

week-12

  1. Space Complexity and its Complexity Classes Video
  2. Logspace Reductions and NL-Completeness Video
  3. Savitch's theorem Video
  4. Results in Space Complexity Video
  5. Summary and Concluding Remarks Video

Live Session

  1. Live Session 22-04-2025 Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Hyderabad
Department
Computer Science and Engineering
Teacher
Prof. Subrahmanyam Kalyanasundaram
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge. Coordinated by IIT Madras.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed