Academic year(s): 2018-2019
SCOTCAT credits : 15
ECTS credits : 7
Level : SCQF Level 9
This module introduces Turing machines, non-determinism and pushdown automata, followed by study of decidability, simulation and the Halting problem. It builds upon finite state machines, context-free grammars and big-O notation from second year. The complexity classes P, NP, co-NP, NP-hard, etc., are described via analysis of SAT and graph isomorphism. Strengths and limitations of the abstract approach to complexity are discussed, followed by an in-depth introduction to practical complexity: flops, worst- and average-case analysis, approximate solutions, and case studies.
Pre-requisite(s): Before taking this module you must pass CS2002 and ( pass CS2101 or pass CS2001 )
Anti-requisite(s): You cannot take this module if you take MT3852
Weekly contact: 2 lectures (x 11 weeks) and fortnightly tutorial.
Scheduled learning hours: 28
Guided independent study hours: 122
As used by St Andrews: 2-hour Written Examination = 60%, Coursework = 40%
As defined by QAA
Written examinations : 60%
Practical examinations : 0%
Re-assessment: 2-hour Written Examination = 60%, Existing Coursework = 40%