The University of Southampton
Courses

MATH2014 Algorithms

Module Overview

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 relating 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). 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.

Aims and Objectives

Module Aims

To design algorithms for solving a wide range of problems, and to understand whether or not an algorithm may be implemented so that it has a reasonable computation time.

Learning Outcomes

Knowledge and Understanding

Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:

  • Analyse the worst-case running time of an algorithm
  • Understand why algorithms for a range of problems including sorting, shortest path, network flow, matchings, produce the correct solution, and apply these algorithms to given instances
  • Understand the concept of NP-completeness and its implications
Subject Specific Practical Skills

Having successfully completed this module you will be able to:

  • Design an algorithm for certain types of problem
Subject Specific Intellectual and Research Skills

Having successfully completed this module you will be able to:

  • Derive worst-case performance bounds for some simple algorithms

Syllabus

Basic concepts. Definition and specification of algorithms. Computational complexity and asymptotic estimates of running time. Sorting algorithms and divide and conquer algorithms. Graphs and networks. Basic graph theory definitions. Algorithms for the reachability problem in a graph. Spanning trees. Algorithms for finding a minimum-cost spanning tree in a graph. Shortest paths. Algorithms for finding one or more shortest paths in graph with nonnegative arc or general arc lengths but not negative length circuits. Network flow algorithms. Flows in capacitated networks, algorithms to find the maximum flow in a network and max-flow min-cut theorems. Matchings. Weighted and unweighted matchings in bipartite graphs, algorithms to find a maximum weight/cardinality matching, the Koenig-Egervary theorem and its relationship with the vertex cover problem. Computational complexity theory. The P and NP classes. Polynomial reductions. NP-completeness and NP-hardness. Exponential-time algorithms. Implicit enumeration and branch and bound algorithms. Approximation algorithms. Elements of approximation algorithms.

Learning and Teaching

Teaching and learning methods

Lectures, problems class, private study

TypeHours
Independent Study150
Total study time150

Resources & Reading list

Assignment Problems. Background reading

Algorithms. Background reading

There is no required book, although the following book provides some useful background reading. 

Assessment

Summative

MethodPercentage contribution
Test 20%
Written exam 80%

Referral

MethodPercentage contribution
Exam %

Repeat Information

Repeat type: Internal & External

Linked modules

Pre-requisites

To study this module, you will need to have studied the following module(s):

CodeModule
MATH1049Linear Algebra II
MATH1048Linear Algebra I
MATH1056Calculus
Share this module Facebook Google+ Twitter Weibo

We use cookies to ensure that we give you the best experience on our website. If you continue without changing your settings, we will assume that you are happy to receive cookies on the University of Southampton website.

×