COL352 – Introduction to Automata & Theory of Computation

This fundamental material covered in this course is fairly abstract and theoretical, and will therefore require some mathematical acumen — students should, at the very least, be able to write and understand rigorous formal proofs, especially those involving various kinds of induction. Various discrete maths concepts like closures, cardinality etc. will also feature strongly, so students should be familiar with these as well. The COL202 (Discrete Mathematical Structures) course is a strict prerequisite.

• Minor: 25%. No re-minor will be conducted. If you miss the minor for a medical reason (with appropriate documentation produced within one week of the minor), the major marks will be scaled up accordingly.

• Major: 35%. The syllabus for the major exam will include everything covered in the course.

• Quizzes: 35–40%. There will be both scheduled and surprise quizzes conducted at various points during the semester. The best n-1 out of n surprise quizzes will be considered. All scheduled quizzes will count towards the final grade. Absence in a quiz is directly marked 0. No make-up quizzes will be conducted.

• In-class tutorial questions: 0–5%.

• Bonus: Asking questions and participating on Piazza and participating in Q&A in the TA-run tutorials: 0– 5%. This incentivizes an intent to learn — for questions to receive a bonus, students must have tried the problem by themselves beforehand and be willing to engage in a discussion with the teaching staff. This bonus will only be added to the final total, and is computed as (100-(your total))/100 * (instances of participation)/5 * constant, with a choice of constant such that this value normalizes to a maximum of 5%.

Audit pass needs at least a B- overall, including at least 25% out of the 35–40% earmarked for quizzes.

Deviation of any sort from the IIT Delhi honour code (copying, plagiarism, collaborating on gradable items where explicitly disallowed etc. – see here and here for more examples) will summarily result in an F grade, or in case of audit, an NF, and potentially further disciplinary action.

We will follow notes presented in class, for the most part, which will be uploaded here. Some external references for much of the course are listed below (caveat emptor: notation used in these books might differ significantly from that used in class).

• Introduction to the theory of computation, by Michael Sipser

• Theory of computation, by Dexter C. Kozen

• Automata and computability, by Dexter C. Kozen