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: 3-hour Examination = 40%, Coursework = 60%


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

Personnel

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