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 |

- 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)

- 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

- "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 announcements, discussion forum, course material
- Gradescope for homework submission and exam feedback

- A passing grade will be decided on the basis of the total of the following.
- 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.

Quizzes | 60 marks | 3 of 4 quizzes; 20 marks each |

End-semester exam | 40 marks |