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 Repeat options
 
Open Pre-Requisites
 
Open Co-Requisites
 
Open Timetable
 
Copyright © 2017 Maynooth University
Maynooth, Co. Kildare, Ireland
Tel: +353(1) 7086000
Powered by MDAL Framework © 2019
V5.2.0 - Powered by MDAL Framework © 2019