Applications for the September 2026 Qualifier will open on June 29, 2026. Notify me
Degree Level Course

Theory of Computation

Theory of computation deals with the encapsulation and abstraction of diverse computational processes, whether hardware or software, which enables us to compare them and understand their basic capabilities and limitations. It is intrinsically related to algorithmic models, where we seek to determine what can and cannot be computed, how quickly, with how much memory, without being bogged down by low-level implementation details. The course will introduce the tools for using and arguing about various fundamental computational questions in a rigorous framework. It will elucidate how formal languages help understanding of core techniques like simulation, reductions, and nondeterminism. Together, it will offer deep understanding of what is hard to compute efficiently and trade-offs between resources like time and space even for the fastest computing machines.

Code BSCS3021
Credits 4 Credits
Type Elective
Prerequisites None
Core Competencies

What You'll Learn

  • Understand formal models of computation including finite-state machine and pushdown automata and associated languages

  • Understand the concept of non-determinism

  • Design and simulate Turing Machines to explore the boundaries of computability

  • Analyze computational complexity

  • Use reductions to relate problems to argue about computability, NP-Completeness and the limits of efficient computation

  • Appreciate the landscape of complexity theory

  • Develop formal reasoning and proof skills

12-Week Roadmap

Course Structure & Syllabus

For details of standard term assessment timelines and exam structures, visit our Academics page.

WEEK 1
Introduction to Theory of Computation with Finite Automata.
WEEK 2
Regular Languages and Regular Expressions.
WEEK 3
Regular Languages, DFA Minimization, and Pumping Lemma.
WEEK 4
Context-Free Languages (CFLs) and Parse Trees.
Faculty & Experts

About the Instructors

Prof. Partha Pratim Das

Prof. Partha Pratim Das

Professor , Department of Computer Science and Founding Director, Center for Data Science and Analytics , Ashoka University

Dr. Das obtained his B Tech, M Tech and Ph D degrees in1984, 1985 and 1988 respectively from IIT Kharagpur. He served as a faculty member in the Department of Computer Science and Engineering, IIT Kharagpur from 1988 to 1998. In 1998, he moved to the Industry and served in Senior Director positions. In 2011, Dr. Das joined back the Department as a Professor. He is the Joint PI of National Digital Library of India project of MoE and leads the national initiative to integrate the digital learning contents.

Dr. Das is a regular contributor to the SWAYAM Program and his courses on Programming in C++, Object Oriented Analysis and Design, and Data Base Management Systems have been attended by thousands of students since 2017. Over the last decade he has been teaching Compilers, Software Engineering, Image Processing, Foundations of Algorithms & Machine Learning, and Principles of Programming Languages for which he received top students’ feedback 6 times during 2014 to 2018. Dr. Das has published over 50 papers in international journals in his interest areas spanning Computer Vision, Digital Learning, Digital Geometry, Human-Computer Interaction, Medical Image Analysis, Computer Analysis of Indian Classical Dance, and Productivity in Software Engineering.