Module Specifications..
Current Academic Year 2023  2024
Please note that this information is subject to change.
 
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 and the mathematics behind these algorithms. They will also interpret the algorithm outputs and translate this into knowledge about the geometry of the original problem and its solution. 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, take inclass tests and do online homework.  
Learning Outcomes 1. Apply algorithms in optimisation problems 2. Demonstrate a knowledge of the mathematics underlying algorithms 3. Interpret algorithm output 4. Construct proofs of simple propositions 5. Determine geometry of optimisation problems from linear algebra computations.  
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 maxflow via simplex method, and via graph search  
 
Indicative Reading List
 
Other Resources None  
Programme or List of Programmes
 
Archives: 
