Theory of Computation

Prof. Subrahmanyam Kalyanasundaram Department of Computer Science and Engineering Indian Institute of Technology Hyderabad ABOUT THE COURSE: This course is an introduction to the theory of computation. We start with computability --- different models of computations and see what are the capabilities of each of these models. Each of these models try to model a computer. We see the classes of languages each of these models are capable of computing. After computability, we will see an introduction to complexity, where we classify computable languages on the basis of easiness/difficulty of computation. The student should be comfortable with basic proof techniques. INTENDED AUDIENCE: This is a core course BTech students in the Computer Science stream. PREREQUISITES: Discrete Mathematics should have been completed. It is also desirable (not mandatory) that the students have done/are doing in parallel the Design and Analysis of Algorithms course. INDUSTRY SUPPORT: As this is a core BTech CS course, this is important for any industry that requires a BTech student who is strong in CS fundamentals To Enroll: https://onlinecourses.nptel.ac.in/noc23_cs31/preview