Module: Optimisation

Module Specifications.

Current Academic Year 2024 - 2025

All Module information is indicative, and this portal is an interim interface pending the full upgrade of Coursebuilder and subsequent integration to the new DCU Student Information System (DCU Key).

As such, this is a point in time view of data which will be refreshed periodically. Some fields/data may not yet be available pending the completion of the full Coursebuilder upgrade and integration project. We will post status updates as they become available. Thank you for your patience and understanding.

Date posted: September 2024

Module Title	Optimisation
Module Code	MS534 (ITS) / MTH1073 (Banner)
Faculty	Science & Health	School	Mathematical Sciences
Module Co-ordinator	Thomas Brady
Module Teachers	-
NFQ level	9	Credit Rating	7.5
Pre-requisite	Not Available
Co-requisite	Not Available
Compatibles	Not Available
Incompatibles	Not Available

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 in-class 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.

*Type*	*Hours*	*Description*
Workload	Full-time hours per semester
Lecture	36	Lecture
Tutorial	12	Tutorial
Independent Study	170	Independent learning
Directed learning	3	Final Exam
Total Workload: 221

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	20%	Examination Weight	80%

Type	Description	% of total	Assessment Date
Course Work Breakdown
In Class Test	6 in-class tests	15%	Every Second Week
Participation	Webwork homework	5%	As required

Reassessment Requirement Type
Resit arrangements are explained by the following categories: Resit category 1: A resit is available for both* components of the module. Resit category 2: No resit is available for a 100% continuous assessment module. Resit category 3: No resit is available for the continuous assessment component where there is a continuous assessment and examination element.
* ‘Both’ is used in the context of the module having a Continuous Assessment/Examination split; where the module is 100% continuous assessment, there will also be a resit of the assessment
This module is category 3

Indicative Reading List

Eugene Lawler: 2001, Combinatorial optimization, Dover Publications, Mineola, N.Y., 0486414531
Hamdy A. Taha,: 0, Operations Research: An Introduction, 9780132555937
David G. Luenberger, Yinyu Ye (Contributor): 0, Linear and Nonlinear Programming, 978-1441945044

Other Resources

None