Theory of Computation COMP3630

Course overview

Course description

This course covers the theoretical computer science areas of formallanguages and automata, computability and complexity. Topics covered include: regular and context-free languages; finite automata and pushdown automata; Turing machines; Church's thesis; computability - halting problem, solvable and unsolvable problems; space and time complexity; classes P, NP and PSPACE; NP-Completeness.

Textbooks

Hopcropft, J.E., Motwani, R. & Ullman, J.D.Automata Theory, Languages, and Computation 3rd edition, Pearson Education, 2007.