X
X
X

X
Swayam Central

Theory of Computation

By Prof. Ragunath Tewari   |   IIT Kanpur
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 : Upcoming
Course Type : Elective
Duration : 8 weeks
Start Date : 29 Jul 2019
End Date : 20 Sep 2019
Exam Date : 29 Sep 2019
Category :
  • Computer Science and Engineering
  • Level : Undergraduate
    This is an AICTE approved FDP course

    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 2019Morning 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

    DOWNLOAD APP

    FOLLOW US