 Coordinates
 D slot: Mon (11  11.50 am), Tue (10  10.50 am), Wed (9  9.50 am), Thu (1  1.50 pm)
 CS 36
 TAs
 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
 Objectives
 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.
 Contents
 The following is a brief overview of the topics that will be covered in this course. The order of the topics covered may vary.
 FiniteState Machines and Regular Languages: Languages vs Computational problems, Deterministic and nondeterministic finite state automata, regular languages, closure properties, limitations  pumping lemma and MyhillNerode relations, state minimization, equivalent models, algorithmic questions.
 ContextFree Grammars: Grammars, Chomsky hierarchy, normal forms, closure properties, limitations  pumping lemma, algorithmic questions  parsing algorithm, equivalent models  pushdown 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, ChurchTuring thesis.
 Basic Complexity Theory  Measures of complexity, complexity classes P and NP, notion of polynomialtime reducibility, NPcompleteness, satisfiability and Cook's theorem.
 References
 [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,
Apr 23  Quizzes: Feb 20,
Mar 26  End sem:
May 6
 Short exams: Feb 6, Mar 12,
 Course materials
 Firstday handout
 Moodle
 Lectures and references
 Problem sets and tutorials: P1, T1, P2, P3, P4, P5, P6 The lectures after March 16th, and the remaining five problem sets are available on Moodle.