|Prerequisites||CS208 Logic & Algorithms|
|Availability||Semesters 1 and 2|
|Contact||Lectures: 22 | Tutorials: 11 | Labs: 0
Assignments: 88 | Self study: 79
|Assessment||30% by coursework, 70% by written examination.|
|Lecturer||Dr Sergey Kitaev|
Aims and Objectives
Building on the previous material in software development, to extend and to formalise the student’s abilities in the area of computational complexity.
On completion of the class, a student should be able:
- to categorise abstract machines and to construct machines appropriate to specific problems
- to display an understanding of the merits and limitations of the analytical techniques of software development
- to recognise the significance of complexity classes and analysis and to deduce the complexity of certain types of algorithm
- to demonstrate a deeper and broader understanding of classes of complexity and of the ability to deduce the complexity of specific algorithms
- to display an extended ability to determine the complexity of software by the application of analytical techniques
- to demonstrate practical competence in the range of issues associated with the class
Introduction: the need for formality in the analysis of problems in computation.
Computation by Abstract Machines: classification, finite automata, deterministic and non-deterministic machines, Turing Machines, the halting problem, solvable, semi-solvable and unsolvable problems.
Recursive functions: basic and primitive recursive functions, partial and total recursive functions.
Analysis of Algorithms: complexity of algorithms, divide and conquer, analysing certain algorithms, pairwise comparison problems, matrix multiplication problems, introduction to NP-completeness.
Complexity Theory & its Implications: towards more efficient software; divide and conquer revisited and dynamic programming; matrix multiplication, transitive closure, problems reducible to matrix multiplication; comparison problems – finding the nth largest; the Fast Fourier Transform; NP-completeness.
Students will be required to undertake, as private study, significant practical work associated with the issues of the class.
* This list is indicative only – the class lecturer may recommend alternative reading material. Please do not purchase any of the reading material listed below until you have confirmed with the class lecturer that it will be used for this class.