Registry

Module Specifications

Current Academic Year 2012 - 2013
Please note that this information is subject to change.

Module Title	Optimisation
Module Code	MS415
School	School of Mathematics
Online Module Resources
Module Co-ordinator	Semester 1: Thomas Brady Semester 2: Thomas Brady Autumn: Thomas Brady
Module Teacher	Thomas Brady
NFQ level	8	Credit Rating	7.5
Pre-requisite	None
Co-requisite	None
Compatibles	None
Incompatibles	None

Description

This module provides an introduction to combinatorial optimisation. In this module students will develop knowledge and skills in the basic combinatorial algorithms applied to optimisation. The participants are expected to have a good knowledge of linear algebra and experience with the abstract approach to mathematics. This module provides the first steps in the discipline known as operations research. Students are expected to attend lectures, participate in tutorials and take in-class tests.

Learning Outcomes

1. Apply algorithms in optimisation problems
2. Demonstrate a knowledge of the geometry underlying linear programming
3. Interpret algorithm output
4. Construct proofs of simple propositions

Workload	Full-time hours per semester
*Type*	*Hours*	*Description*
Lecture	36	Lecture
Tutorial	12	Tutorial
Independent learning time	172	Independent earning
Total Workload: 220

All module information is indicative and subject to change. For further information,students are advised to refer to the University's Marks and Standards and Programme Specific Regulations at: http://www.dcu.ie/registry/examinations/index.shtml

Indicative Content and Learning Activities

Graphs.
Graphs, trees, shortest path algorithms, greedy algorithm, matroids.

Polytopes.
Polytopes, Farkas' Lemma, linear programming, the geometry of linear inequalities.

Matchings.
matching problems, bipartite matching, weighted matching.

Network flow.
max-flow via simplex method, and via graph search.

Assessment Breakdown
Continuous Assessment	25%	Examination Weight	75%

Course Work Breakdown
Type	Description	% of total	Assessment Date
In Class Test	In Class test	25%	Every Second Week

Reassessment Requirement
Resit arrangements are explained by the following categories; 1 = A resit is available for all components of the module 2 = No resit is available for 100% continuous assessment module 3 = No resit is available for the continuous assessment component
This module is category 3

Indicative Reading List

Eugene Lawler: 2001, Combinatorial optimization, Dover Publications, Mineola, N.Y., 0486414531
Hamdy A. Taha,: 2010, Operations Research: An Introduction, 9th, Prentice-Hall, 9780132555937

Other Resources

None

Array

Programme or List of Programmes

ACM

BSc Actuarial Mathematics

APM

B.Sc. Applicable Mathematics

BSc in Financial & Actuarial Mathematics

IFPFIM

Pre-Masters Intl. Foundation Programme

Timetable this semester: Timetable for MS415