# Theory of Computation - Institution: IIT Hyderabad - Department: Computer Science and Engineering - Teacher: Prof. Subrahmanyam Kalyanasundaram - Level: Undergraduate - Language: English - Subjects: Computer science, Engineering - Source: [NPTEL](https://nptel.ac.in/courses/106106242) - Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.) - Syllabus: [at the source](https://nptel.ac.in/courses/106106242) - Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words) ## Lectures 1. [An Introduction to The Theory of Computation](https://invisiblenetwork.ai/learn/nptel/106106242/284438072169) (Video) 2. [Notations and Terminology in Theory of Computation](https://invisiblenetwork.ai/learn/nptel/106106242/57b29aebade6) (Video) 3. [An Introduction to Finite Automata and Regular Languages - Part 01](https://invisiblenetwork.ai/learn/nptel/106106242/4ad0cdc10c30) (Video) 4. [An Introduction to Finite Automata and Regular Languages - Part 02](https://invisiblenetwork.ai/learn/nptel/106106242/df94485cc610) (Video) 5. [Significance of Regular Languages and Regular Operations](https://invisiblenetwork.ai/learn/nptel/106106242/00097406cdaa) (Video) 6. [Closure Properties of Regular Languages Under Union, Concatenation and Kleene Star Operation-Part 01](https://invisiblenetwork.ai/learn/nptel/106106242/701f0efa5c0e) (Video) 7. [Closure Properties of Regular Languages Under Union, Concatenation and Kleene Star Operation-Part 02](https://invisiblenetwork.ai/learn/nptel/106106242/ca65b32044bf) (Video) 8. [An Introduction to Non-Deterministic Finite Automata (NFA)](https://invisiblenetwork.ai/learn/nptel/106106242/8feb4609a271) (Video) 9. [Formal Definitions and Examples of Non-Deterministic Finite Automata(NFA)](https://invisiblenetwork.ai/learn/nptel/106106242/0da76b9a9a28) (Video) 10. [Equivalence of NFA and DFA](https://invisiblenetwork.ai/learn/nptel/106106242/1d4dc5737464) (Video) 11. [Closure of Regular Languages Under Regular Operations(Using NFA)](https://invisiblenetwork.ai/learn/nptel/106106242/161e239c8bb7) (Video) 12. [Regular Expressions - Part 01](https://invisiblenetwork.ai/learn/nptel/106106242/361d0a5f53a7) (Video) 13. [Regular Expressions - Part 02](https://invisiblenetwork.ai/learn/nptel/106106242/a51a383a33bc) (Video) 14. [Proving Equivalence of Regular Expression and DFA Through a GNFA](https://invisiblenetwork.ai/learn/nptel/106106242/944e70c09163) (Video) 15. [Pumping Lemma for Regular Languages - Part 01](https://invisiblenetwork.ai/learn/nptel/106106242/0d40b772aaee) (Video) 16. [Pumping Lemma for Regular Languages - Part 02](https://invisiblenetwork.ai/learn/nptel/106106242/6ab08ec5f444) (Video) 17. [Distinguishability of Strings and Myhill-Nerode Theorem](https://invisiblenetwork.ai/learn/nptel/106106242/f68f19ff563a) (Video) 18. [Proving the Myhill-Nerode Theorem](https://invisiblenetwork.ai/learn/nptel/106106242/adc51ee17cf7) (Video) 19. [An Introduction to Context-Free Languages - Part 01](https://invisiblenetwork.ai/learn/nptel/106106242/3c5fabab9d19) (Video) 20. [An Introduction to Context-Free Languages - Part 02](https://invisiblenetwork.ai/learn/nptel/106106242/8b512a83f38f) (Video) 21. [Chomsky Normal Form](https://invisiblenetwork.ai/learn/nptel/106106242/74fb9e80a969) (Video) 22. [CYK Algorithm - Part 1](https://invisiblenetwork.ai/learn/nptel/106106242/cf1b0885abe4) (Video) 23. [CYK Algorithm - Part 2 (Example)](https://invisiblenetwork.ai/learn/nptel/106106242/bb08f0c7ec77) (Video) 24. [Closure Properties of Context Free Languages](https://invisiblenetwork.ai/learn/nptel/106106242/da239b39a057) (Video) 25. [An Introduction to Push Down Automata](https://invisiblenetwork.ai/learn/nptel/106106242/de9c603812e6) (Video) 26. [Normalizations in PDA and Intersection of Regular Language & CFL](https://invisiblenetwork.ai/learn/nptel/106106242/d05cbc92944d) (Video) 27. [Equivalence of Context Free Grammars and Push Down Automata - Part 01](https://invisiblenetwork.ai/learn/nptel/106106242/4fc11dbcccba) (Video) 28. [Equivalence of Context Free Grammars and Push Down Automata - Part 02](https://invisiblenetwork.ai/learn/nptel/106106242/0c38ed91077c) (Video) 29. [Equivalence of Context Free Grammars and Push Down Automata - Part 03](https://invisiblenetwork.ai/learn/nptel/106106242/9882011e4403) (Video) 30. [Pumping Lemma for Context Free Languages](https://invisiblenetwork.ai/learn/nptel/106106242/6a510c265e91) (Video) 31. [Examples of Pumping Lemma Usage for Context Free Languages](https://invisiblenetwork.ai/learn/nptel/106106242/8e4568b8d73b) (Video) 32. [Formal Definition of a Turing Machine](https://invisiblenetwork.ai/learn/nptel/106106242/77afdd8a8782) (Video) 33. [Turing Recognizable & Decidable Languages and TM Examples](https://invisiblenetwork.ai/learn/nptel/106106242/cb91dad77e67) (Video) 34. [Multitape Turing Machine](https://invisiblenetwork.ai/learn/nptel/106106242/6f3ef649cbd1) (Video) 35. [Non-Deterministic Turing Machines](https://invisiblenetwork.ai/learn/nptel/106106242/bdd28d055c20) (Video) 36. [Equivalence of Deterministic and Nondeterministic TM](https://invisiblenetwork.ai/learn/nptel/106106242/360768a55cc6) (Video) 37. [Church-Turing Thesis](https://invisiblenetwork.ai/learn/nptel/106106242/40b1bc806a58) (Video) 38. [Decidable Problems Concerning Regular Languages](https://invisiblenetwork.ai/learn/nptel/106106242/7b5026be8037) (Video) 39. [Decidable Problems Concerning Context Free Languages](https://invisiblenetwork.ai/learn/nptel/106106242/aa69108bf465) (Video) 40. [Countability of Sets](https://invisiblenetwork.ai/learn/nptel/106106242/c7eb47e3fe44) (Video) 41. [Proof of Existence of Undecidable Languages](https://invisiblenetwork.ai/learn/nptel/106106242/e0f4b1544bf2) (Video) 42. [Halting Problem](https://invisiblenetwork.ai/learn/nptel/106106242/ac70826331e4) (Video) 43. [Co-Turing Recognizability](https://invisiblenetwork.ai/learn/nptel/106106242/2dcd43084f8a) (Video) 44. [An Introduction to Mapping Reducibility](https://invisiblenetwork.ai/learn/nptel/106106242/4f80d901247a) (Video) 45. [Examples of Proving Undecidability Using Reductions](https://invisiblenetwork.ai/learn/nptel/106106242/a1b332f56b2c) (Video) 46. [Rice Theorem](https://invisiblenetwork.ai/learn/nptel/106106242/57604772a697) (Video) 47. [Computation Histories](https://invisiblenetwork.ai/learn/nptel/106106242/1f52c1a7664c) (Video) 48. [The Post Correspondence Problem](https://invisiblenetwork.ai/learn/nptel/106106242/10b977b5e27a) (Video) 49. [Checking Ambiguity in CFG is Undecidable](https://invisiblenetwork.ai/learn/nptel/106106242/27a20a5302bd) (Video) 50. [Time Complexity - Part 1](https://invisiblenetwork.ai/learn/nptel/106106242/eb6287ec1f8f) (Video) 51. [Time Complexity - Part 2](https://invisiblenetwork.ai/learn/nptel/106106242/7b04b7bb2745) (Video) 52. [Non-Deterministic Polynomial Time - Part 1](https://invisiblenetwork.ai/learn/nptel/106106242/86bc8642c5d1) (Video) 53. [Non-Deterministic Polynomial Time - Part 2](https://invisiblenetwork.ai/learn/nptel/106106242/4b2793b4b409) (Video) 54. [Verifiability and NP](https://invisiblenetwork.ai/learn/nptel/106106242/6fead47a7659) (Video) 55. [Polynomial Time Reductions - Part 1](https://invisiblenetwork.ai/learn/nptel/106106242/b484d733329e) (Video) 56. [Polynomial Time Reductions - Part 2](https://invisiblenetwork.ai/learn/nptel/106106242/8f2b9fb59bec) (Video) 57. [NP-Completeness](https://invisiblenetwork.ai/learn/nptel/106106242/4f09ad9d64d9) (Video) 58. [Cook-Levin Theorem](https://invisiblenetwork.ai/learn/nptel/106106242/18c928a7cadb) (Video) 59. [Cook-Levin Theorem - Proof and Implications](https://invisiblenetwork.ai/learn/nptel/106106242/9e15cb17989e) (Video) 60. [CLIQUE and VERTEX-COVER is NP-Complete](https://invisiblenetwork.ai/learn/nptel/106106242/28480c6323a7) (Video) 61. [HAM-PATH is NP-Complete](https://invisiblenetwork.ai/learn/nptel/106106242/f66133f69bd5) (Video) 62. [SUBSET-SUM is NP-Complete](https://invisiblenetwork.ai/learn/nptel/106106242/2e603bdf8a93) (Video) 63. [Knapsack Problem](https://invisiblenetwork.ai/learn/nptel/106106242/f344e22212cf) (Video) 64. [Integer Linear Program is NP-Complete](https://invisiblenetwork.ai/learn/nptel/106106242/776d1ea4ce9e) (Video) 65. [Space Complexity and its Complexity Classes](https://invisiblenetwork.ai/learn/nptel/106106242/d0a0dd88ac54) (Video) 66. [Logspace Reductions and NL-Completeness](https://invisiblenetwork.ai/learn/nptel/106106242/d54be97f95d3) (Video) 67. [Savitch's theorem](https://invisiblenetwork.ai/learn/nptel/106106242/7b920c7d09f1) (Video) 68. [Results in Space Complexity](https://invisiblenetwork.ai/learn/nptel/106106242/5b1044eff385) (Video) 69. [Summary and Concluding Remarks](https://invisiblenetwork.ai/learn/nptel/106106242/bf4a6d1348a8) (Video) 70. [Live Session 22-04-2025](https://invisiblenetwork.ai/learn/nptel/106106242/284438072169-2) (Video)