COMP2210: Theory of Computing

What the module covered

This module studied computation through mathematical models. It covered regular languages and finite automata, context-free grammars and pushdown automata, and Turing machines. We used constructions and proofs to relate these models and establish their limitations.

The later material covered decidability, the halting problem, reductions, and complexity classes such as P, NP, and PSPACE. This extended algorithm analysis from the cost of a particular implementation to the difficulty of the problem itself.

What I took from it

The key distinction was between a problem that has an expensive solution and one that cannot be solved by a general algorithm at all. Reductions also provide a way to reason about a new problem by relating it to one whose computational limits are already understood.