This course covers the theoretical computer science areas of formal languages and automata, computability and complexity. Topics covered include the following: regular and context-free languages; finite automata and pushdown automata; Turing machines; computability - halting problem, solvable, and unsolvable problems; space and time complexity; classes P, NP and PSPACE; NP-Completeness.
Learning Outcomes
Upon successful completion, students will have the knowledge and skills to:
- Demonstrate advanced knowledge of formal computation and its relationship to languages
- Distinguish different computing languages and classify their respective types
- Recognise and comprehend formal reasoning about languages
- Demonstrate a competent understanding of the basic concepts of complexity theory