University of St Andrews

Key information

SCOTCAT credits : 15

ECTS credits : 7

Level : SCQF level 9

Semester: 2

Availability restrictions: Not available to Joint Honours Mathematics and Computer Science students.

Planned timetable: 10.00 am Mon (even weeks), Tue, Thu.

This module begins with finite state machines, context-free grammars and big-O notation. Turing machines, non-determinism and pushdown automata are introduced, followed by studies on decidability, simulation and the Halting problem. 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 introduction to practical complexity.

Relationship to other modules

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

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

Learning and teaching methods and delivery

Weekly contact: 2 hours of lectures (x 11 weeks), .5-hour tutorial (x 10 weeks)

Scheduled learning hours: 27

Guided independent study hours: 123

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 = 100%

Personnel

Module teaching staff: Prof C Roney-Dougal, Dr S Sarkar, Prof Ian Gent, Prof S Linton