COMPUTATION & COMPLEXITY
- Module code: CS370
- Credits: 5
- Semester: 1
- Department: COMPUTER SCIENCE
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.
On successful completion of the module, students should be able to:
|Teaching & Learning methods|
Timetable under review
The Lectures timetable allows you to search by most courses that are offered by the University.
The Venues timetable allows you to search the timetable by venue.
The Departments timetable allows you to search the timetable by department.
The Students timetable is a personalised timetable. The student is required to login using their Student ID and Password.