CS 310 : Automata Theory 2019

Instructors : S. Akshay and Ashutosh Gupta

Timings : 9:30 Monday, 10:35 Tuesday, 11:35 Thursday
Venue : CC103
TAs : Adarsh Rahul Jaju (173050003@), Kalyani Dole (163050022@), Kunal Mittal (kunal@cse), Mukesh Pareek (pareek@cse), Prachi Singh (183050075@), Swapnam Bajpai (swapnam@cse), Vaibhav Krishan (vkrishan@cse), Meet Taraviya (meet11061997 _at_ gmail.com)
For email addresses Append ".iitb.ac.in" in the text inside the parenthesis
Optional problem solving/help sessions : 7PM, Thursday@CC103

Source material

Evaluation structure

Tutorial sheets

Lectures (23 onwards)

Details of the first part of the course, i.e., Lectures 1 -- 22, can be found here

04-03-2019 : Lecture 23 - Turing machines

05-03-2019 : Lecture 24 - Turing machines and computability

07-03-2019 : Lecture 25 - Variants of Turing machines

11-03-2019 : Lecture 26 - Turing recognizability and decidability

12-03-2019 : Lecture 27 - Turing machines and Undecidability

14-03-2019 : Lecture 28 - Reductions

18-03-2019 : Lecture 29 - Reductions (contd.)

19-03-2019 : Lecture 30 - Rice's theorem

25-03-2019 : Lecture 31 - Rice's theorem (contd.)

26-03-2019 : Lecture 32 - Post's Correspondance Problem

28-03-2019 : Lecture 33 - PCP and Undecidable problems for CFLs

01-04-2019 : Lecture 34 - Linear Bounded Automata

02-04-2019 : Lecture 35 - Efficient Computation

04-04-2019 : Lecture 36 - Running time complexity

08-04-2019 : Lecture 37 - Polynomial time complexity

09-04-2019 : Lecture 38 - Non-deterministic time complexity classes

11-04-2019 : Lecture 39 - P vs NP, SAT, Ptime-reductions

15-04-2019 : Lecture 40 - NP completeness

16-04-2019 : Lecture 41 - SAT is NP complete

18-04-2019 : Lecture 42 - Introduction to space complexity


Last modified: ()