Theory of Computation

By Prof. Ragunath Tewari | IIT Kanpur

Learners enrolled: 7769

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: Content will be updated soon

Summary

Course Status :	Completed
Course Type :	Elective
Duration :	8 weeks
Category :	Computer Science and Engineering
Credit Points :	2
Level :	Undergraduate
Start Date :	29 Jul 2019
End Date :	20 Sep 2019
Exam Date :	29 Sep 2019 IST

Note: This exam date is subjected to change based on seat availability. You can check final exam date on your hall ticket.

Page Visits

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

Books and references

Introduction to the Theory of Computation by Michael Sipser

Instructor bio

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 certificate

The course is free to enroll and learn from. But if you want a certificate, you have to register and write the proctored exam conducted by us in person at any of the designated exam centres.
The exam is optional for a fee of Rs 1000/- (Rupees one thousand only).
Date and Time of Exams: 29 September 2019, Morning session 9am to 12 noon; Afternoon Session 2pm to 5pm.
Registration url: Announcements will be made when the registration form is open for registrations.
The online registration form has to be filled and the certification exam fee needs to be paid. More details will be made available when the exam registration form is published. If there are any changes, it will be mentioned then.
Please check the form for more details on the cities where the exams will be held, the conditions you agree to when you fill the form etc.

CRITERIA TO GET A CERTIFICATE

Average assignment score = 25% of average of best 6 assignments out of the total 8 assignments given in the course.
Exam score = 75% of the proctored certification exam score out of 100
Final score = Average assignment score + Exam score

YOU WILL BE ELIGIBLE FOR A CERTIFICATE ONLY IF AVERAGE ASSIGNMENT SCORE >=10/25 AND EXAM SCORE >= 30/75.

If one of the 2 criteria is not met, you will not get the certificate even if the Final score >= 40/100.
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.
Only the e-certificate will be made available. Hard copies are being discontinued from July 2019 semester and will not be dispatched

SWAYAM Helpline / Support