COMP36111 Algorithms and Complexity syllabus 2021-2022
36111-cwk1-F-Formulating Arguments; Out of 20; Deadline End Wk II Oct 4th 14:00 36111-cwk2-S-exercisesA; Out of 20; Deadline End Wk IV Oct 18th 14:00 36111-cwk3-S-exercisesB; Out of 20; Deadline End Wk IX Nov 22nd 14:00
Through coursework in weeks 4, 7 and 10
- Lectures (22 hours)
- Analytical skills
- Problem solving
On successful completion of this unit, a student will be able to:
- To understand the standard hierarchy of commonly-encountered complexity classes defined in relation to the Turing model of computation.
- To understand the concepts of (problem-) reduction and computational hardness, and to develop familiarity with techniques for establishing lower complexity bounds---especially, NPTime-hardness.
- To be familiar with the most important and central theorems in Complexity Theory (Cook's theorem, Ladner's theorem, Savitch's theorem the Immerman-Szelepcsenyi theorem).
- To be able to access and understand the scientific literature in regard to Complexity Theory.
- To be able to analyse the computational complexity of a range of problems.
|Computational complexity : a modern approach||Arora, Sanjeev.||0521424267 (hbk.) :; 9780521424264 (hbk.) :||Cambridge University Press||2009.|
|Introduction to the theory of computation||Sipser, Michael.||9781133187813||Cengage Learning||c2013.|
|Algorithm design and applications||Goodrich, Michael T., author.||9781119028482||John Wiley Inc.||2015|
Course unit materials
Links to course unit teaching materials can be found on the School of Computer Science website for current students.