CS3052 Computational Complexity

Academic year

2023 to 2024 Semester 2

Further information on which modules are specific to your programme.

Key module information

SCOTCAT credits

15

The Scottish Credit Accumulation and Transfer (SCOTCAT) system allows credits gained in Scotland to be transferred between institutions. The number of credits associated with a module gives an indication of the amount of learning effort required by the learner. European Credit Transfer System (ECTS) credits are half the value of SCOTCAT credits.

SCQF level

SCQF level 9

The Scottish Credit and Qualifications Framework (SCQF) provides an indication of the complexity of award qualifications and associated learning and operates on an ascending numeric scale from Levels 1-12 with SCQF Level 10 equating to a Scottish undergraduate Honours degree.

Planned timetable

To be arranged.

This information is given as indicative. Timetable may change at short notice depending on room availability.

Module Staff

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

This information is given as indicative. Staff involved in a module may change at short notice depending on availability and circumstances.

Module description

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-requisites

BEFORE TAKING THIS MODULE YOU MUST PASS CS2002 AND PASS CS3050 AND ( PASS CS2101 OR PASS CS2001 )

Anti-requisites

YOU CANNOT TAKE THIS MODULE IF YOU TAKE MT3852

Assessment pattern

3-hour Examination = 40%, Coursework = 60%

Re-assessment

3-hour Examination = 40%, Coursework = 60%

Learning and teaching methods and delivery

Weekly contact

2 lectures (x 11 weeks) and fortnightly tutorial.

Scheduled learning hours

28

The number of compulsory student:staff contact hours over the period of the module.

Guided independent study hours

122

The number of hours that students are expected to invest in independent study over the period of the module.