CS2200 Languages, Machines and Computation
Jan - May 2020
- D slot: Mon (11 - 11.50 am), Tue (10 - 10.50 am), Wed (9 - 9.50 am), Thu (1 - 1.50 pm)
- CS 36
- 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)
- Office hours
- Yadu: Wednesdays, 2 - 3.30 pm
- 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.
- Grading policy
- Pop quizzes: 5%
- Short exams: 3*5 = 15%
- Quizzes: 2*20 = 40%
- End sem: 40%
- Important dates
- Short exams: Feb 6, Mar 12,
- Quizzes: Feb 20,
- End sem:
- Course materials