CS411 - Theory of Computation
| TIMETABLE | TEACHING MATERIAL |
| Credits | 20 |
| Level | 4 |
| Semester | Semester 2 |
| Availability | Not available as elective |
| Prerequisites | CS208 - Logic & Algorithms |
| Learning Activities Breakdown | Lectures: 20 | Tutorials: 10 | Labs: 0 Assignments: 80 | Self study: 90 |
| Assessment | 30% by coursework, 70% by written examination. |
| Lecturer | Clemens Kupke |
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.
Learning Outcomes
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
Syllabus
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.
Recommended Reading
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.
Introduction to the Theory of Computation (Second Edition, International Edition). Michael Sipser. Thomson Course Technology 2006. ISBN 0-6192-1764.
Computers and Intractability: A Guide to the Theory of NP-Completeness. Michael R. Garey and David S. Johnson. W. H. Freeman and Company 1979. ISBN 0-7167-1045-5
Last updated: 2022-09-09 13:42:04