IITM BS Theory of Computation (BSCS3021): Syllabus and Tips

Theory of Computation (BSCS3021) is a 4 credit elective at the degree level of the IITM BS in Data Science. It asks what computers can and cannot do. You study simple machine models like finite automata, then Turing machines, then which problems are unsolvable or too hard to solve quickly. The course page lists no prerequisite. It is a proof based course, not a coding course.

Theory of Computation at a glance

The instructor is Prof. Partha Pratim Das of Ashoka University. The course page lists the type as "Elective".

One mismatch you should know about: this course does not appear in the DS handbook's degree level course table (updated 18 March 2026). So the handbook gives no stream tag and no list of terms when it runs. By the handbook's code rule, a 3xxx code means a level 3 course. Before you plan around it, confirm with support that it is offered in your term and how its credits count.

What you learn in Theory of Computation

The 12 weeks move from the simplest machines to the hardest questions.

• Weeks 1 to 3: finite automata and regular languages. What a finite automaton is, regular languages and regular expressions, how to shrink a DFA to its smallest form, and the pumping lemma for showing a language is not regular.
• Weeks 4 to 6: context-free languages. Grammars and parse trees, pushdown automata that recognise these languages, languages that are not context-free, and a first look at Turing machines.
• Weeks 7 to 9: what can be computed at all. Variants of Turing machines, the Church Turing thesis, decidable and undecidable problems, and using reductions to prove a problem is undecidable.
• Weeks 10 to 12: what can be computed quickly. Time and space complexity, polynomial time reductions, hard problems and NP completeness.

The page lists no textbook.

How it is assessed

The course page does not spell out the assessment for this course. It only points to the programme's standard course structure. Check the course page and your course portal at the start of the term.

Where it counts

It is a degree level elective, so its 4 credits can go towards your elective credits. It is not part of any minor. Because it is missing from the handbook table, it is not clear which stream it counts for. Being level 3, it would not fill the level 4 or higher stream slots at the BS degree level. For the courses the handbook does list, see DS degree level electives.

Who finds it hard and how to prepare

The difficulty is proofs. Most of your earlier courses asked you to compute an answer or write code. Here you must argue in steps why a language is not regular, or why a problem cannot be decided. If you have never written a proof, the pumping lemma and reductions will feel slow at first.

• Build proof habits first. Mathematical Thinking (BSMA2001) covers proofs, sets and Cantor's diagonal argument, a common tool in undecidability proofs. Discrete Mathematics (BSMA3001) covers logic, induction and proof methods.
• Draw machines by hand. For each small language, sketch a DFA and test it on five strings that should pass and five that should fail.
• Use a template for pumping lemma proofs. Write the same steps every time: assume regular, pick the string, split it, pump, reach a contradiction.
• Keep a reduction map. Every time you see a reduction, write "A reduces to B" and what it proves. The pattern repeats in the complexity weeks.
• Explain one idea aloud each week. If you cannot explain a week's main result in plain words, revise that week again.

What to take before and after

Before: PDSA from the diploma, and one of the proof courses above. After: Advanced Algorithms (BSCS4021) picks up NP hardness and shows ways to cope with hard problems. Compiler Design (BSCS4032), from the same instructor, applies regular expressions, finite automata and grammars to build a working compiler.

Common questions

Is Theory of Computation in the handbook's list of electives?

No. It is not in the DS handbook's degree level course table updated on 18 March 2026. The official course page exists, so ask support whether it is open for registration in your term.

Do I need to write programs in this course?

The course page lists designing and simulating Turing machines, which is closer to drawing and tracing than to coding. It does not mention an OPPE or a programming exam.

How is this different from Advanced Algorithms?

Both touch NP completeness. Theory of Computation asks what can be computed at all and builds formal machine models. Advanced Algorithms is about designing fast algorithms and coping with hard problems.

Which level does BSCS3021 count at?

The handbook says the first digit of the course number gives the level. BSCS3021 is therefore a level 3 course.