Course Details in

Module Title	LM Combinatorial Optimisation
School	Mathematics
Department	Mathematics
Module Code	06 20442
Module Lead	Dr P Butkovic
Level	Masters Level
Credits	10
Semester	Semester 2
Pre-requisites	Linear Programming and Symmetry and Groups - (06 22503) Linear Programming, Symmetry and Groups - (06 22491)
Co-requisites
Restrictions	Optional for MSci programmes in Mathematics, MSci programmes with Major in Mathematics, MSci programmes with Joint (60 credits) in Mathematics
Contact Hours	Lecture-23 hours Tutorial-5 hours Total: 28 hours
Exclusions
Description	This module develops some of the ideas introduced in Management Mathematics and will continue to encourage interest in practical problems. The module presents a systematic survey of methods of optimisation for problems with discrete features and relates them to rpactical problems such as finding the cheapest route through a transportation network or efficiently assigning resources to objectives. The concept of computational complexity leads to a classification of problems into grades of hardness and to the concept of the efficiency of an algorithm.
Learning Outcomes	By the end of the module the student should be able to: Formulate practical problems as discrete optimisations and apply exact or approximate algorithms to problems like shortest path, network flows, transportation, knapsack and travelling salesman problems Demonstrate an understanding of computational complexity and its reduction and of proofs that certain problems are NP hard Explore this topic beyond the taught syllabus
Assessment	20442-01 : Raw Module Mark : Coursework (100%)
Assessment Methods & Exceptions	90% based on a 1.5 hour written examination in the Summer Term; 10% based on work during term-time.
Other
Reading List