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
ABOUT THE INSTRUCTOR
Raghunath Tewari is an Associate Professor in the department of Computer Science and Engineering at IIT Kanpur. His research interests lie in the areas of computational complexity theory, algorithms and graph theory.
Additional information
Institute
IITK
Total hours
20
Certification Process
1. Join the course
Learners may pay the applicable fees and enrol to a course on offer in the portal and get access to all of its contents including assignments. Validity of enrolment, which includes access to the videos and other learning material and attempting the assignments, will be mentioned on the course. Learner has to complete the assignments and get the minimum required marks to be eligible for the certification exam within this period.
COURSE ENROLMENT FEE: The Fee for Enrolment is Rs. 2000 + GST
2. Watch Videos+Submit Assignments
After enrolling, learners can watch lectures and learn and follow it up with attempting/answering the assignments given.
3. Get qualified to register for exams
A learner can earn a certificate in the self paced course only by appearing for the online remote proctored exam and to register for this, the learner should get minimum required marks in the assignments as given below:
CRITERIA TO GET A CERTIFICATE
Assignment score = Score more than 50% in at least 6/8 assignments.
Exam score = 50% of the proctored certification exam score out of 100
Only the e-certificate will be made available. Hard copies will not be dispatched.”
4. Register for exams
The certification exam is conducted online with remote proctoring. Once a learner has become eligible to register for the certification exam, they can choose a slot convenient to them from what is available and pay the exam fee. Schedule of available slot dates/timings for these remote-proctored online examinations will be published and made available to the learners.
EXAM FEE: The remote proctoring exam is optional for a fee of Rs.1500 + GST. An additional fee of Rs.1500 will apply for a non-standard time slot.
5. Results and Certification
After the exam, based on the certification criteria of the course, results will be declared and learners will be notified of the same. A link to download the e-certificate will be shared with learners who pass the certification exam.
CERTIFICATE TEMPLATE
Course Details
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
akash patil –
well teching skills