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 |

- 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, 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.