Theory of Computation

Course code	COL352
Instructor	Ashish Chiplunkar (ashishc@iitd...)
Teaching Assistants	Ajay Soni (mcs202446@cse...), Indrajit Banerjee (csy207569@cse...), Prashant Agrawal (csz188011@cse...), Shivansh Juyal (mcs202471@cse...), Sukriti Gupta (cs5160084@cse...), Vijay Bhardwaj (mcs202476@cse...)
Classes	Monday and Wednesday 11:00 - 12:00, Thursday 12:00 - 13:00 (Slot H)
Office hour	TBD

Prerequisites

COL202 or MTL180 or an equivalent course. Specifically, the following topics:

Finite state machines and finite automata, nondeterminism, regular languages and their properties, regular expressions, pumping lemma for regular languages, Myhill-Nerode theorem, minimal automata
Grammars, ambiguity, context-free languages and their properties, pumping lemma for context-free languages, pushdown automata
Turing machines, deciders, multi-tape and non-deterministic Turing machines, Turing-recognizability and decidability, enumerators
Undecidability and un-recognizability, mapping reductions, Rice's theorem
Time-complexity, P and NP, Karp-reductions, NP-hardness and NP-completeness, Cook-Levin theorem

"Introduction to the Theory of Computation" by Michael Sipser
"Elements of the Theory of Computation" by Harry Lewis and Christos Papadimitriou
"Automata and Computability" by Dexter Kozen

Microsoft Teams for live lectures (check the 'Lectures' channel)
Impartus for recorded lectures (see the 'Flipped Lectures' tab) and notes / slides (see the 'Backpack' tab)
Moodle, Piazza for announcements and discussions
Gradescope for exams

Forum contribution	5%	Any technical post on Moodle / Piazza / MSTeams that could potentially benefit most of the class counts.
Homeworks	25%	30+ questions with binary marking distributed across 5-6 homeworks; best 25 scores count.
Quizzes	30%	Best 3 of 4-5 count.
Major exam	40%

30% marks necessary for a passing grade.