Courses / Module

Toggle Print

Module COMPUTATION & COMPLEXITY

Module code: CS370
Credits: 5
Semester: 1
Department: COMPUTER SCIENCE
International: Yes
Overview Overview
 

Computability theory: Turing machines and Church Turing thesis, decidable and recognisable languages, proofs of undecidability, Turing and many-one reducibility, Rice's theorem, the recursion theorem. Computational complexity: measures of complexity and asymptotic analysis. Complexity classes, P and NP; intra-class reductions; complexity analysis (best, worst, average case) of algorithms. More complexity classes, nondeterminism; NP-hardness, NP-completeness.

Open Learning Outcomes
 
Open Teaching & Learning methods
 
Open Assessment
 
Open Autumn Supplementals/Resits
 
Open Pre-Requisites
 
Open Co-Requisites
 
Open Timetable
 
Back to top Powered by MDAL Framework © 2022
V5.3.3 - Powered by MDAL Framework © 2022