Jan - May 2020
- Where: CS 36
- When: D slot (Mon 11-11.50, Tue 10-10.50, Wed 9-9.50, Thu 13-13.50)
- Anil Kumar S (cs18d001@smail)
- Anoop S K M (cs18d003@smail)
- Athul M A (cs19m015@smail)
- Govind Sankar (ee16b109@smail)
- Sampriti Roy (cs18s007@smail)
- Sreyas S (cs18d010@smail)
This course provides an introduction to the mathematical theory of computation. The course gives a preliminary exposure to theoretical computer science, and the formal relationships among machines and computational problems with the aim of understanding the nature of computation and its inherent limits.
The following is a brief overview of the topics that will be covered in this course. The order of the topics covered may vary.
- Finite-State Machines and Regular Languages: Languages vs Computational problems, Deterministic and non-deterministic finite state automata, regular languages, closure properties, limitations - pumping lemma and Myhill-Nerode relations, state minimization, equivalent models, algorithmic questions.
- Context-Free Grammars: Grammars, Chomsky hierarchy, normal forms, closure properties, limitations - pumping lemma, algorithmic questions - parsing algorithm, equivalent models - push-down automata.
- Computability Theory - Turing machines, equivalence between different variants, Universal Turing machine, recursively enumerable and recursive sets of languages, Decidability - Halting Problem, Post’s correspondence problem, Rice’s theorem, Church-Turing thesis.
- Basic Complexity Theory - Measures of complexity, complexity classes P and NP, notion of polynomial-time reducibility, NP-completeness, satisfiability and Cook’s theorem.
- [K]: Automata and Computability - Dexter C. Kozen
- [HMU]: Introduction to Automata Theory, Languages and Computation - Hopcroft, Motwani and Ullman.
- [S]: Introduction to the Theory of Computation - Michael Sipser
- Pop quizzes: 5%
- Short exams: 3*5 = 15%
- Quizzes: 2*20 = 40%
- End-sem: 40%
- Short exams: Feb 6, Mar 12
- Quizzes: Feb 20
- Lectures and references