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.

by Prof. Partha Pratim Das

Course ID: BSCS3021

Course Credits: 4

Course Type: Elective

Pre-requisites: None

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

Course structure & Assessments

For details of standard course structure and assessments, visit 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.
WEEK 5 Pushdown Automata and Recognizers of CFLs.
WEEK 6 Non-CFLs and Introduction to Turing Machines.
WEEK 7 Variants of Turing Machines and the Church–Turing Thesis.
WEEK 8 Decidability and Undecidable Problems.
WEEK 9 Reductions and Proving Undecidability.
WEEK 10 Time and Space Complexity.
WEEK 11 Polynomial-Time Reductions and Hard Problems.
WEEK 12 NP-Completeness and Course Summary.
+ Show all weeks

About the Instructors

Prof. Partha Pratim Das
Professor, Computer Science and Engineering, IIT Kharagpur

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.

...  more

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.

  less

Other courses by the same instructor: BSCS2001 - Database Management Systems

View all Degree Level courses

support@study.iitm.ac.in
7850999966
IITM BS Degree Office, 3rd Floor,
ICSR Building, IIT Madras,
Chennai - 600036

Please use only the above methods for program queries. Response time: 3 working days. During peak periods, Google Meet links will be shared. Call wait times may be longer.

Terms of Service | Privacy Policy