DCU Home | Our Courses | Loop | Registry | Library | Search DCU


Module Specifications

Archived Version 2016 - 2017

Module Title
Module Code

Online Module Resources

NFQ level 8 Credit Rating 7.5
Pre-requisite None
Co-requisite None
Compatibles None
Incompatibles None

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
Independent Study170Independent earning
Directed learning2Final Exam
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, trees, shortest path algorithms, greedy algorithm, matroids

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

matching problems, bipartite matching, weighted matching

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

Assessment Breakdown
Continuous Assessment% Examination Weight%
Course Work Breakdown
TypeDescription% of totalAssessment Date
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
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

Programme or List of Programmes