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. |
Learning Outcomes | |
---|---|
Teaching & Learning methods | |
---|---|
Assessment | |
---|---|
Autumn Supplementals/Resits | |
---|---|
Timetable | |
---|---|