|Prerequisites||CS208 Logic & Algorithms|
|Contact||Lectures: 20 | Tutorials: 10 | Labs: 0
Assignments: 80 | Self study: 90
|Assessment||30% by coursework, 70% by written examination.|
|Lecturer||Professor Radu Mardare|
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.
Analysis of Algorithms and Complexity Theory: Measuring complexity of algorithms, Big-O and Small-o notations, analysing certain algorithms, polynomial time algorithms, the PATH problem, tree searchers (depth-first search & breadth-first search), the HAMPATH problem, the Composites problem, the class NP, polynomial time reducibility, the CLIQUE problem, NP-completeness, the Cook-Levin Theorem.
* 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.