CDS 303: Theory of Computation
Fall 2026
- Instructor: Satyabrata Jana ( satyabrataj [at] iiserbpr [dot] ac [dot] in )
- Timings: Monday (5 – 6 PM), Tuesday (2 – 3 PM), Friday (2 – 3 PM)
- Venue: Room No. 2006, 2nd Floor, Block 6
- Grading: End-Sem Exam (40%), Mid-Sem Exam (30%), Assignments (20%), Attendance (10%)
Objectives
This course introduces the fundamental concepts of the Theory of Computation, including formal languages, automata, computability, and computational complexity. Students will study different models of computation and understand their capabilities and limitations. The course also examines the relationships among various classes of languages and computational problems. Emphasis will be placed on developing analytical reasoning, mathematical rigour, and proof-writing skills.
Prerequisites
Students are expected to be comfortable with basic mathematical reasoning, elementary set theory, functions, relations, and standard proof techniques such as induction and proof by contradiction.
References
- Introduction to the Theory of Computation – Michael Sipser
- Introduction to Automata Theory, Languages, and Computation – John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
- Automata and Computability – Dexter C. Kozen
- An Introduction to Formal Languages and Automata – Peter Linz, Susan H. Rodger
- Elements of the Theory of Computation – Harry R. Lewis, Christos H. Papadimitriou
- Introduction to Theory of Computation – Anil Maheshwari, Michiel Smid
- Automata, Computability and Complexity: Theory and Applications – Elaine Rich
- Theory of Computer Science: Automata, Languages and Computation – K. L. P. Mishra, N. Chandrasekaran
- Theory of Computation: Automata, Languages, Complexity – Supantha Pandit, Jagpreet Singh
Lectures
- Lecture 1 (03.08.2026): Introduction to the course.