Part A: Course Overview

Course Title: Graph Algorithms and Applications

Credit Points: 12.00

Terms

Course Code

Campus

Career

School

Learning Mode

Teaching Period(s)

MATH2308

City Campus

Undergraduate

171H School of Science

Face-to-Face

 Sem 2 2018,
Sem 2 2020

Course Coordinator: Dr Marc Demange

Course Coordinator Phone: +61 3 9925 2385

Course Coordinator Email: marc.demange@rmit.edu.au

Course Coordinator Location: 15.04.14

Course Coordinator Availability: by appointment


Pre-requisite Courses and Assumed Knowledge and Capabilities

MATH1150 Discrete Mathematics or equivalent (in particular a basic introduction to discrete structures and to proof techniques) and MATH2313 Problem solving and algorithms or equivalent (in particular a basic introduction to algorithmic methods)

The course is designed such that MATH1288 Operations Research 1 or equivalent (introduction to linear programming) is not a pre-requisite. Relevant notions will be introduced when useful. However, students with a background in linear programming will be proposed voluntary and unassessed activities crossing both topics.


Course Description

This course aims to provide you with a broad knowledge of graph and other combinatorial methods used in Operations Research. These approaches are complementary to (integer) linear programming approaches. There will be an emphasis on discussing types of graph models for a broad range of problems; characterising the underlying mathematical problems;  comparing these models to (integer) linear programming models; discussing the advantages and disadvantages of each one; and establishing a framework for selecting the appropriate solution technique. The notions of efficient algorithms will be discussed and the notion of complexity of a problem will be briefly addressed. You will also be introduced to the use of computer techniques for solving such problems.

 

Topics will include a broad range of areas for example:

  1. Optimal path problems, graph methods for project management (CPM) and dynamic programming
  2. Flows in networks, Maximum flow/Minimum cut, transportation and assignment problems
  3. Minimum spanning tree problem
  4. Introduction to graph colouring


Objectives/Learning Outcomes/Capability Development

 

This course contributes to the following Program Learning Outcomes for BP083 Bachelor of Science, BP245 Bachelor of Science (Statistics) and BH119 Bachelor of Analytics (Honours):

Knowledge and technical competence:

  • use the appropriate and relevant, fundamental and applied mathematical and statistical knowledge, methodologies and modern computational tools.

Problem-solving:

  • synthesise and flexibly apply knowledge to characterise, analyse and solve a wide range of problems
  • balance the complexity / accuracy of the mathematical / statistical models used and the timeliness of delivery of the solution.

Teamwork and project management

  • contribute to professional work settings through effective participation in teams and organisation of project tasks
  • constructively engage with other team members and resolve conflict.

Communication

  • communicate both technical and non-technical material in a range of forms (written, electronic, graphic, oral) and tailor the style and means of communication to different audiences. Of particular interest is the ability to explain technical material, without unnecessary jargon, to lay persons such as the general public or line managers.

Information literacy

  • locate and use data and information and evaluate its quality with respect to its authority and relevance.


 

On completion of this course you should be able to:

  1. Apply the knowledge and skills obtained to investigate and solve a variety of combinatorial optimisation problems
  2. Address unfamiliar problems and propose, analyse and apply one or several relevant models to generate a solution.
  3. Compare different models for a single problem, discriminate the most relevant depending on the objective and identify its limitations.
  4. Select and use relevant software to launch and interpret experiments.
  5. Communicate both technical and non-technical material in a range of forms (written, oral, electronic, graphic) using  language and format accessible to a variety of audiences.
  6. Contribute to professional work settings through effectively participating in teams and organising project tasks.


Overview of Learning Activities

Theoretical concepts and methodologies will be  presented and illustrated in interactive lectures

Supervised tutorials will reinforce the material covered in lectures and build your capacity to model real problems and analyse related mathematical problems. Practical computer exercises will provide the skills necessary to select and use appropriate technologies. Your group project will help you to develop communication, professional and teamwork skills as you develop a business case.

Assessment activities include class exercises (to be completed outside of class time), a class test, a group project and a final exam.

Teacher Guided Hours: 48 per semester, Learner Directed Hours: 72 per semester


Overview of Learning Resources

All course material will be provided online through myRMIT Studies. These resources will include lecture notes on selected topics, slides, articles, internet links, videos and exercises.

Additional supporting documents can be found at http://rmit.libguides.com/mathstats and http://rmit.libguides.com/compsci


Overview of Assessment

 Assessment Tasks:

 

Early Assessment Task: Assignment 1

A problem discussed in class and completed at home.

Weighting 7.5%

This assessment task supports CLOs 1, 2, 3

 

Assessment Task 2: Assignments 2

Problems discussed in class and completed at home.

Weighting 7.5%

This assessment task supports CLOs 1, 2, 3

 

Assessment Task 3:  Class Test

Weighting 15%

This assessment task supports CLO 1, 2, 3

 

Assessment Task 4: Group project

Weighting 25%

This assessment supports CLOs 1, 2, 3, 4, 5, 6

 

Assessment 5: Final Exam

Weighting 45%

This assessment supports CLOs 1, 2, 3