Module description
Aims and Learning Outcomes
This module introduces the basic concepts of computational mathematics.
On successful completion of this module, students will:
Be able to:
- Reason about solvability and complexity of problems
- Model and solve practical problems by using the taught methods
- design efficient algorithms for different problems in computer science
Syllabus
An indication of the type of topics:
Computational Models and Complexity:
- Turing Machines
- Decidability and recognisability
- Mapping reductions
- Complexity classes: P, NP, co-NP
- Polynomial reductions
- NP-completeness, SAT, and examples of classic NP-complete problems
Graph algorithms:
- Graph traversal algorithms DFS and BFS
- Algorithms based on DFS: Minimum spanning trees, topological sort, strongly connected components and an algorithm for finding maximal strongly connected components, Dijkstra's shortest paths in a graph algorithm
Algorithmic approaches and techniques:
- Greedy algorithms
- Dynamic programming
- Divide and conquer (recurrence relations + analysis via Master Theorem)
- Mixed integer-linear programming (MILP)
- Branch and bound for MILP
- Approximation ratio + examples of approximable and unapproximable problems
- Efficient SAT solving (DPLL)
- Local search: neighbourhoods and local minima
- Relaxation heuristics
Assessment details
Please note: The below assessment details for the 2024/25 academic year may be updated. The confirmed details will be available on the Student Handbook and on the module KEATS page at the beginning of the semester.
Semester 1 only study abroad students will be required to take this exam in an alternative assessment format in the January exam period.
Full year study abroad students will be required to take this exam in person in January.