|Look up fees
At the heart of theoretical computer science are questions of both philosophical and practical importance. What does it mean for a problem to be solvable by computer? What are the limits of computability? Which types of problems can be solved efficiently? What are our options in the face of intractability? This subject covers such questions in the content of a wide-ranging exploration of the nexus between logic, complexity and algorithms, and examines many important (and sometimes surprising) results about the nature of computing.
- Turing machines
- The Church-Turing Thesis
- Decidable languages
- Time Complexity: The classes P and NP, NP-complete problems
- Space complexity: including sub-linear space
- Circuit complexity
- Approximation algorithms
- Probabilistic complexity classes
- Additional topics may include descriptive complexity, interactive proofs, communication complexity, complexity as applied to cryptography
- Space complexity, including sub-linear space
- Finite state automata, pushdown automata, regular languages, context-free languages to the Recommended Background Knowledge.
Example of assignment
- Proving the equivalence of a variant of a standard machine to the original version
- Describing an NP-hardness reduction
- Designing an approximation algorithm for an NP-hard problem.
Intended learning outcomes
INTENDED LEARNING OUTCOMES (ILO)
On completion of this subject the student is expected to:
- Design, manipulate, and reason about Turing machines
- Account for the inherent complexity of many computational problems of practical importance
- Conduct formal reasoning about machines, circuits, problems and algorithms, including reduction-based proof
- Design approximation algorithms for intractable problems
- Apply complexity arguments to related fundamental computational problems, such as randomized computations, interactive proof systems and cryptographic pseudorandom generators
On completion of this subject, students should have developed the following skills:
- Ability to apply knowledge of science and engineering fundamentals
- Ability to communicate effectively, with the engineering team and with the community at large
- Capacity for lifelong learning and professional development
- Profound respect for truth and intellectual integrity, and for the ethics of scholarship.
Last updated: 3 November 2022