CS3021 · BS elective · 4 credits

Theory of Computation

Automata, formal languages, computability and the mathematical limits of what a program can do.

Instructor Prof. Partha Pratim Das Term As offered Prereq MA2001

§ 1Calendar

  • Quiz 1—
  • Quiz 2—
  • End-term examination—

§ 2Previous Year Questions

No papers uploaded yet.

§ 3Resources

CS3021 · BS elective · 4 credits

Syllabus

The official course syllabus, transcribed from the IITM BS Data Science & Applications course booklet.

§ 1Course Description

This course introduces the theory of computation, focusing on abstract models of computation to understand the capabilities and limitations of algorithms. It covers fundamental concepts such as formal languages, simulation, reductions, and nondeterminism, and examines what can be computed efficiently, along with trade-offs between resources like time and space.

Lectures-Tutorials-Practicals-Credits: 4-0-0-4

§ 2Faculty

  • Prof. Partha Pratim Das, Department of Computer Science and Engineering, IIT Kharagpur

§ 3Week-by-week

Week 1: Introduction to theory of computation; Finite automata and formal models.

Week 2: Regular languages; Regular expressions; Language representation.

Week 3: DFA minimization; Pumping lemma; Properties of regular languages.

Week 4: Context-free languages (CFLs); Grammars and parse trees.

Week 5: Pushdown automata (PDA); Recognition of CFLs.

Week 6: Non-context-free languages; Introduction to Turing machines.

Week 7: Variants of Turing machines; Church-Turing thesis.

Week 8: Decidability; Undecidable problems.

Week 9: Reductions; Proving undecidability.

Week 10: Time and space complexity; Complexity classes.

Week 11: Polynomial-time reductions; Hard computational problems.

Week 12: NP-completeness; Course summary and unifying concepts.