Courses / Module

Toggle Print

COMPUTATION AND COMPLEXITY

Module code: CS370FZ
Credits: 5
Semester: 1
Department: INTERNATIONAL ENGINEERING COLLEGE
International:

	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.

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.

	Learning Outcomes
	On successful completion of the module, students should be able to: Explain how some problems have no algorithmic solution. Provide examples that illustrate the concept of uncomputability. Define the classes P and NP. Explain the significance of NP-completeness. Prove that a problem is NP-complete by reducing a classic known NP-complete problem to it.

Teaching & Learning methods

Assessment

	Autumn Supplementals/Resits
	Are supplemental/resit registrations permitted? Yes Is Supplemental Continuous Assessment registration permitted? Yes Is Supplemental Continuous Assessment capped? No

	Timetable
	This timetable is not currently available, please contact the International Engineering College Department.

Search form

Courses / Module

COMPUTATION AND COMPLEXITY