University of St Andrews

Key information

SCOTCAT credits : 15

ECTS credits : 7

Level : SCQF level 9

Semester: 2

Planned timetable: To be arranged.

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.

Relationship to other modules

Pre-requisite(s): Before taking this module you must pass CS2002 and pass CS3050 and ( pass CS2101 or pass CS2001 )

Anti-requisite(s): You cannot take this module if you take MT3852

Learning and teaching methods and delivery

Weekly contact: 2 lectures (x 11 weeks) and fortnightly tutorial.

Scheduled learning hours: 28

Guided independent study hours: 122

Assessment pattern

As used by St Andrews: 2-hour Written Examination = 60%, Coursework = 40%

As defined by QAA
Written examinations : 60%
Practical examinations : 0%
Coursework: 40%

Re-assessment: 2-hour Written Examination = 60%, Existing Coursework = 40%

Personnel

Module teaching staff: TBC Module coordinator(s): Honours Coordinator - Computer Science (hons-coord-cs@st-andrews.ac.uk)