Theory of Computation

Course code	COL352
Instructor	Ashish Chiplunkar (ashishc@iitd...)
Teaching Assistants	Sidharth Agarwal, Lakshay Saggi, Harsh Singh Chauhan, Dhananjay Kumar Jha, Jay Prafulkumar Joshi, Sumit Singh Dhami
Classes	LH108; Monday and Wednesday 11:00 - 12:00, Thursday 12:00 - 13:00 (Slot H)
Tutorials	LH108; Wednesday 18:30 - 19:30

Eligibility

COL202 or MTL180 or an equivalent course is a hard prerequisite; a passing grade in one of these courses is mandatory for registering into COL352. It is equally important that you recall everything taught in the prerequisite course, specifically:

Proof techniques - construction, contradiction, induction
Sets and set operations, relations
Functions -- injections, surjections, and bijections; cardinality
Countability and uncountability, diagonalization
Equivalence relations, partial orders
Asymptotic behavior of functions (O(.) notation)

MTL783 is a known overlapping course. Students who have done or are currently doing MTL783 will be disallowed from taking COL352 for a grade. Students who do COL352 might be disallowed from taking MTL783 in future (attn. MT1, MT6 students). In any case, everyone who is interested in attending COL352 will be allowed to do so. If you are unsure whether you have done or are currently doing any other course with significantly overlapping content, please contact the instructor on Teams.

Content

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, NP-hardness and NP-completeness, Cook-Levin theorem
Depending on the available time and interest, some of the following topics: Polynomial hierarchy, Time hierarchy theorems, Space complexity and related classes, Probabilistic Turing machines

Textbooks

"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

It is not mandatory to buy any of the above books if you plan to attend classes and tutorial sessions regularly.

Useful Platforms

Microsoft Teams for announcements, discussion forum, course material
Gradescope for homework submission and exam feedback

Grading and Attendance Policy

A passing grade will be decided on the basis of the total of the following.

Quizzes	60 marks	3 of 4 quizzes; 20 marks each
End-semester exam	40 marks

Quizzes will be announced a week in advance.
Quiz 4 will be a compensatory / improvement quiz intended for students who miss or perform poorly in Quizzes 1-3. If Quiz 4 is not attempted, marks of Quizzes 1-3 will be counted. If Quiz 4 is attempted, its marks will be counted with the marks of the best 2 of Quizzes 1-3. The decision about whether to attempt Quiz 4 must be taken before the quiz (it cannot be taken after reading the question paper). Beyond this, no compensation for missed quizzes will be given.
In every exam, students will be allowed to use both sides of a single A4 sheet as a cheat sheet; no other reference material is allowed.
Practice problems will be given regularly, and will be discussed in the tutorial sessions. Some of them will be designated as homework problems. Homework problems will have a binary marking. These marks will not count towards the grade, but will count towards the passing criterion. Homework deadlines will not be extended under any circumstances. Submission of homeworks copied from others will obviously be treated as academic dishonesty.
Passing criterion: Let x be the marks obtained out of 100 in quizzes and the end-semester exam. Let y be the marks obtained out of z in homeworks. A passing grade will be given if and only if x >= 30 or (x+y) >= 0.3*(100+z). (The grade will be determined by x only.)
No audits. Every auditing student will get an NF grade.
Penalty for insufficient attendance: students with insufficient attendance (<75%) will not be allowed to write the re-major exam (in case they get an E grade), and their I grade requests will be turned down (in case they miss the end-semester exam and apply for an I grade). Other than this, there is no pentalty for insufficient attendance. Assuming you pass the course, grade and attendance will be conditionally independent given marks. (However, rest assured that unconditionally, grade and attendance will be heavily correlated!) Marking attendance in lectures and tutorials is nevertheless mandatory. Marking attendance without attending will be treated as academic dishonesty.