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
- Introduction to Automata Theory, Languages, and Computation. John Hopcroft, Rajeev Motwani, and Jeffrey Ullman
- Introduction to the Theory of Computation. Michael Sipser
Evaluation structure
- Attendance (via random tests, pop-quizzes etc): 5%
- Quizzes : 30% (4 quizzes)
- Midterm : 25% (2 hours)
- Final : 40% (3 hours)
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
- Definition of Turing machines, examples
- slides
- Suggested reading : Hopcroft Ullman Sec 8.2, Sipser Chap.3
05-03-2019 : Lecture 24 - Turing machines and computability
- Definition of Turing recognizability, decidability, The Church-Turing thesis
- slides
- Suggested reading : Hopcroft Ullman Sec 8.2, Sipser Chap.3
07-03-2019 : Lecture 25 - Variants of Turing machines
- Variants of Turing machines, multiple-tapes, non-deterministic TM
- slides
- Suggested reading : Hopcroft Ullman Sec 8.4, 8.5, Sipser Chap.3
11-03-2019 : Lecture 26 - Turing recognizability and decidability
- Turing machines as strings, Decidability
- slides
- Suggested reading : Hopcroft Ullman Sec 9.1, Sipser Chap.3, 4
12-03-2019 : Lecture 27 - Turing machines and Undecidability
- Undecidability and a proof by diagonalization
- slides
- Suggested reading : Hopcroft Ullman Sec 9.1, 9.2, Sipser Chap.4
14-03-2019 : Lecture 28 - Reductions
- More Undecidability and reductions
- slides
- Suggested reading : Hopcroft Ullman Sec 9.3, Sipser Chap.5
18-03-2019 : Lecture 29 - Reductions (contd.)
- More undecidability proofs by reduction
- slides
- Suggested reading : Hopcroft Ullman Sec 9.3, Sipser Chap.5
19-03-2019 : Lecture 30 - Rice's theorem
- Rice's theorem, its proof and its applications
- slides
- Suggested reading : Hopcroft Ullman Sec 9.3
25-03-2019 : Lecture 31 - Rice's theorem (contd.)
- Rice's theorem, its proof and applications; other undecidable problems
- slides
- Suggested reading : Hopcroft Ullman Sec 9.3, 9.4
26-03-2019 : Lecture 32 - Post's Correspondance Problem
- Post's Correspondance Problem (PCP) and a proof by reduction
- slides
- Suggested reading : Hopcroft Ullman Sec 9.4, Sipser Chap 5
28-03-2019 : Lecture 33 - PCP and Undecidable problems for CFLs
- Completing the proof of undecidability of PCP and applying PCP to show undecidability of ambiguity for CFGs
- slides
- Suggested reading : Hopcroft Ullman Sec 9.4, 9.5, Sipser Chap. 5
01-04-2019 : Lecture 34 - Linear Bounded Automata
- Between PDA and TM: Linear Bounded Automata and their properties
- slides
- Suggested reading : Sipser Chap. 5
02-04-2019 : Lecture 35 - Efficient Computation
- Resource bounded Turing machines: memory and time, running time complexity, asymptotic complexity
- slides
- Suggested reading : Hopcroft Ullman Sec 8.4, Sipser Chap. 7
04-04-2019 : Lecture 36 - Running time complexity
- Running time complexity, multi-tape vs single-tape revisited
- slides
- Suggested reading : Hopcroft Ullman Sec 8.4, Sipser Chap. 7
08-04-2019 : Lecture 37 - Polynomial time complexity
- Non-determinism vs determinism, polynomial and exponential time complexity classes.
- slides
- Suggested reading : Hopcroft Ullman Sec 8.4, 10.1, Sipser Chap. 7
09-04-2019 : Lecture 38 - Non-deterministic time complexity classes
- The NP class, Non-deterministic polynomial time vs deterministic polynomial time verifiers.
- slides
- Suggested reading : Hopcroft Ullman Sec 8.4, 10.1, Sipser Chap. 7
11-04-2019 : Lecture 39 - P vs NP, SAT, Ptime-reductions
- P vs NP, the satisfiability problem (SAT), Polynomial-time reductions
- slides
- Suggested reading : Hopcroft Ullman Sec 10.1, 10.2, Sipser Chap. 7
15-04-2019 : Lecture 40 - NP completeness
- NP completeness and the Cook-Levin theorem: SAT is NP complete
- slides
- Suggested reading : Hopcroft Ullman Sec 10.2, Sipser Chap. 7
16-04-2019 : Lecture 41 - SAT is NP complete
- Completing the proof of NP-hardness of SAT, getting around NP-hardness
- slides
- Suggested reading : Hopcroft Ullman Sec 10.2, Sipser Chap. 7
18-04-2019 : Lecture 42 - Introduction to space complexity
- A brief introduction to space complexity classes, Quiz 4 problem solving and tips
- slides
- Suggested reading : Hopcroft Ullman Sec 11.2, Sipser Chap. 8.2
Last modified: ()