Neural Sync Active
BSCS3021 - Theory of Computation
Registry Synced
BSCS3021 - Theory of Computation
543 words
3 min read
| Field | Value |
|---|---|
| Course Code | BSCS3021 |
| Level | Degree Level Course |
| Credits | 4 |
| Type | Elective |
| Pre-requisites | None |
📖 Description
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.
🗓️ Weekly Syllabus
| Week | Topic |
|---|---|
| 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. |
📝 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