Theory of Computation Course | IIT Hyderabad | Prof. Subrahmanyam Kalyanasundaram
Course Details
| Exam Registration | 957 |
|---|---|
| Course Status | Ongoing |
| Course Type | Core |
| Language | English |
| Duration | 12 weeks |
| Categories | Computer Science and Engineering |
| Credit Points | 3 |
| Level | Undergraduate |
| Start Date | 19 Jan 2026 |
| End Date | 10 Apr 2026 |
| Enrollment Ends | 02 Feb 2026 |
| Exam Registration Ends | 20 Feb 2026 |
| Exam Date | 18 Apr 2026 IST |
| NCrF Level | 4.5 — 8.0 |
Unlocking the Foundations of Computing: A Deep Dive into the Theory of Computation
What are the fundamental limits of what computers can and cannot do? How do we classify problems based on their inherent difficulty? The Theory of Computation provides the rigorous mathematical framework to answer these profound questions. It is the bedrock of computer science, separating mere programming from a deep understanding of the field's core principles.
This detailed guide outlines a structured 12-week undergraduate journey through this fascinating subject, based on a course designed and taught by an expert from one of India's premier institutions.
Your Guide: Expert Instruction from IIT Hyderabad
This course is presented by Prof. Subrahmanyam Kalyanasundaram, an Associate Professor in the Department of Computer Science and Engineering at IIT Hyderabad. With a rich academic background including a Masters from IISc and a Ph.D. in Algorithms, Combinatorics and Optimization from Georgia Tech, Prof. Kalyanasundaram brings over a decade of teaching and research experience to the table. His interests span combinatorics, graph theory, and theoretical computer science, ensuring a course grounded in deep expertise.
Who Is This Course For?
Intended Audience: This is a core course designed primarily for undergraduate (BTech) students in the Computer Science and Engineering stream.
Prerequisites: A solid foundation in Discrete Mathematics is essential. It is also highly beneficial, though not mandatory, to have completed or be concurrently taking a course in the Design and Analysis of Algorithms.
Industry Relevance: This course is fundamental for any technology-driven industry seeking graduates with strong CS fundamentals. It develops critical analytical and problem-solving skills crucial for roles in advanced software development, research, cryptography, and artificial intelligence.
Course Overview: From Computability to Complexity
The course is strategically divided into two major segments:
- Computability: We begin by exploring different models of computation (like Finite Automata, Pushdown Automata, and Turing Machines) to understand what it means for a problem to be “computable” at all. We examine the classes of languages (problems) each model can handle.
- Complexity: Once we know a problem is computable, we ask: How efficiently can it be solved? This section introduces complexity theory, where we classify computable problems based on the resources (time, space) required, leading to the famous P vs. NP question.
Detailed 12-Week Course Layout
| Week | Topics Covered |
|---|---|
| Week 1 | Introduction, DFAs, Regular Languages, Closure under Union |
| Week 2 | NFAs, Equivalence to DFAs, Regular Expressions |
| Week 3 | Pumping Lemma, Myhill-Nerode Theorem, Context-Free Grammars |
| Week 4 | Chomsky Normal Form, CYK Algorithm, Pushdown Automata |
| Week 5 | Equivalence of PDAs & CFGs, Pumping Lemma for CFLs, Turing Machines |
| Week 6 | Decidable & Recognizable Languages, Multi-tape & Nondeterministic TMs, Church-Turing Thesis |
| Week 7 | Decidability of CFLs, Countability, The Halting Problem & Undecidability |
| Week 8 | Reductions, Rice’s Theorem, More Undecidable Problems |
| Week 9 | Post Correspondence Problem, Intro to Complexity, P and NP Classes |
| Week 10 | Verifiers, Polynomial-Time Reductions, NP-Completeness, Cook-Levin Theorem |
| Week 11 | Classic NP-Complete Problems: Vertex Cover, Hamiltonian Path, Subset Sum |
| Week 12 | Space Complexity, Complexity Classes L, NL, PSPACE, and Key Relationships |
Essential Reading & Resources
To successfully navigate this course, the following textbooks are highly recommended:
- Introduction to the Theory of Computation by Michael Sipser (often considered the standard text).
- Introduction to Automata Theory, Languages and Computation by Hopcroft, Motwani, and Ullman.
Embarking on this 12-week journey through the Theory of Computation will transform your understanding of computer science. You will move from seeing a computer as a tool to understanding it as a mathematical concept with defined powers and limitations. This knowledge is not just academic; it is the key to innovating at the very frontiers of what is computationally possible.
Enroll Now →