X
X
X

X
Courses » Theory of Computation

Theory of Computation

ABOUT THE COURSE

This is an introductory course on Theory of Computation intended for undergraduate students in computer science. In this course we will introduce various models of computation and study their power and limitations. We will also explore the properties of the corresponding language classes defined by these models and the relations between them. We will assume the student is comfortable in analytical reasoning and has preferably done a course on Data Structures and Algorithms.

INTENDED AUDIENCE

Computer Science undergraduate students.

PRE-REQUISITES

It is recommended that the candidate has done a course in Data Structures and Algorithms.

INDUSTRY SUPPORT – LIST OF COMPANIES/INDUSTRY THAT WILL RECOGNIZE/VALUE THIS ONLINE COURSE

content will be updated soon.

5037 students have enrolled already!!

COURSE INSTRUCTOR



Dr. Raghunath Tewari is an Assistant Professor in the department of Computer Science and Engineering at the Indian Institute of Technology, Kanpur. His primary research interest is in the area of computational complexity theory. Dr. Tewari did his B.Sc. from Chennai Mathematical Institute in 2005 and Ph.D. from University of Nebraska-Lincoln in 2011.
COURSE LAYOUT

    Week 1: Finite Automata – deterministic and nondeterministic, regular operations
    Week 2: Regular Expression, Equivalence of DFA, NFA and REs, closure properties
    Week 3: Non regular languages and pumping lemma, DFA Minimization,
    Week 4: CFGs, Chomsky Normal Form
    Week 5: Non CFLs and pumping lemma for CFLs, PDAs,  Equivalence of PDA and CFG
    Week 6: Properties of CFLs, DCFLs, Turing Machines and its variants
    Week 7: Configuration graph, closure properties of decidable languages, decidability properties of regular languages and CFLs
    Week 8: Undecidability, reductions, Rice's Theorem, introduction to complexity theory


SUGGESTED READING

Introduction to the Theory of Computation by Michael Sipser.


MORE DETAILS ABOUT THE COURSE
Course url: https://onlinecourses.nptel.ac.in/noc16_cs14
Course duration :  8 Weeks
Start date and end date of course:  18 July 2016 - 9 September 2016
Dates of exams : 18 Sep 2016 and 25 Sep 2016
Time of exam : 2pm - 5pm
Final List of exam cities will be available in exam registration form.
Exam registration url - Will be announced shortly
Exam Fee: The online registration form has to be filled and the certification exam fee of approximately Rs 1000(non-Programming) needs to be paid.

CERTIFICATE

E-Certificate will be given to those who register and write the exam. Certificate will have your name, photograph and the score in the final exam. It will have the logos of NPTEL and IIT Kanpur.

It will be e-verifiable at nptel.ac.in/noc.