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.

8649 students have enrolled already!!

COURSE INSTRUCTOR 



Dr.Ragunath 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/noc17_cs34
Course duration :  8 Weeks
Start date and end date of course: 24 July 2017 - 15 September 2017
Dates of exams : 24 Sep 2017
Time of exam : Shift1: 9AM - 12 Noon Shift2 : 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 and score greater than or equal to 40% final score. 

Final score = 25% assignment score + 75% exam score
25% assignment score is calculated as 25% of average of scores of Best 6 out of 8 assignments

Certificate will have your name, photograph and the score in the final exam with the breakup. It will have the logos of NPTEL and IIT Kanpur. It will be e-verifiable at nptel.ac.in/noc.