Algorithms are systematic methods for solving mathematical problems, such as sorting numbers in ascending order, finding the cheapest way to ship goods on the road network or finding the shortest path in a graph. They can be regarded as practical applications of mathematical proofs, and also as theoretical models of computational techniques. This module introduces some basic concepts related to algorithms, their implementation and their efficiency, using simple examples drawn from many areas of mathematics including Graph Theory and Operational Research (no previous knowledge of these topics is required, but having taken MATH1058 may help). The main aim of the module is designing algorithms for solving a wide range of problems, studying their computational complexity, and understanding whether a given problem may or may not admit an efficient algorithm for its solution.
Pre-requisites: MATH1048 and MATH1059