Learning Outcomes
To understand the hierarchy of problems and the associated hierarchy of algorithms.
To learn how algorithms correspond to formal computing machines (finite automata, pushdown automata, Turing machines) while problems correspond to formal languages (regular, context free, recursive)
To be able to study the computational complexity of various key algorithms and classify problems on the basis of their algorithmic complexity (classes P, NP, NP complete, EXP).
To study the issues of undecidability.
Course Content (Syllabus)
1. Relations, alphabets, strings, languages.
2. Computational complexity.
3. Regular expressions and languages.
4. Finite automata.
5. Context free grammars and languages.
6. Pushdown automata.
7. Turing machines.
8. Recursive languages.
9. Decidability.
10. P, NP, NP complete, EXP problems.