ECM3906 - Graphs, Networks and Algorithms (2023)

Back | Download as PDF
MODULE TITLEGraphs, Networks and Algorithms CREDIT VALUE15
MODULE CODEECM3906 MODULE CONVENERDr Mark Callaway (Coordinator)
DURATION: TERM 1 2 3
DURATION: WEEKS 0 11 0
Number of Students Taking Module (anticipated) 20
DESCRIPTION - summary of the module content

Graphs are a structure used to describe the underlying connectedness of a system and, therefore, have a vast range of applications from designing circuit boards to running a business efficiently. In this module, you will learn the theory of graphs and explore their practical application to solve a range of mathematical problems.

Real life problems typically involve enormous graphs, so a key theme in this module will be solving problems efficiently. In particular, some seemingly small and simple problems are so computationally complex that, even in this era of supercomputers, it would take longer than the lifetime of the universe to find a solution. Through analysing the effectiveness and computational complexity of algorithms, you will learn how to refine your proposed solution methods to optimise their performance.

Whilst there are no formal prerequisites, you should be familiar with material from the core undergraduate mathematics curriculum at Exeter, including the theory of sets and functions, analysis, linear algebra and mathematical proof.

Pre-requisites: ECM2902

 

AIMS - intentions of the module
The aim of the module is to present the central results of modern graph theory together with the algorithms used to solve network problems. Whilst accurate computation is essential and will be the focus of the computer-marked quizzes, the lectures and exam will focus on a rigorous development of theory and its application in a range of guided and unseen problems. There will be a particular emphasis on studying the correctness of algorithms (i.e. how do you know it does what you want?) and their complexity (i.e. how quickly does it do it?) in the context of network problems. A project element will allow students to demonstrate their understanding of a subtopic through independent investigation.
 
INTENDED LEARNING OUTCOMES (ILOs) (see assessment section below for how ILOs will be assessed)

On successful completion of this module you should be able to:

 

Module Specific Skills and Knowledge

1 Perform algorithms and routine computations in the theory of graphs and networks accurately;
 
2 State and apply key definitions and results in the theory of graphs and networks;
 
3 Prove core theorems in graph theory;
 
4 Translate problems into a network format for solution;
 
5 Analyse the effectiveness and computational complexity of algorithms for solving network problems;
 
6 Recognise problems that are computationally complex and require heuristic solution methods.

 

Discipline Specific Skills and Knowledge

7 Discuss and use the material from this module in the context of the wider mathematics curriculum;
 
8 Develop independently and with minimal guidance material relevant to this topic.

 

Personal and Key Transferable / Employment Skills and Knowledge

9 Communicate effectively your knowledge of this topic;
 
10 Work independently to develop your knowledge in this subject.

 

SYLLABUS PLAN - summary of the structure and academic content of the module

Topics will be chosen from:

- Basic graph theory: definitions, subgraphs, Euler tours and Hamiltonian cycles, representation of graphs;

- Shortest paths and spanning trees;

- Flows and the max-flow-min-cut theorem;

- Minimal-cost feasible-flow problems;

- The marriage theorem;

- Graph colouring and applications;

- Connectivity and search in graphs;

- Matchings and weighted matchings;

- Postman problems and the salesman problem;

- Graphic embedding and planar decomposition;

- Analytic graph theory and discrete differential geometry;

- Electrical networks and rectangle tilings;

- Additional topics will be considered depending on the interests of the student cohort.

 

LEARNING AND TEACHING
LEARNING ACTIVITIES AND TEACHING METHODS (given in hours of study time)
Scheduled Learning & Teaching Activities 33.00 Guided Independent Study 117.00 Placement / Study Abroad 0.00
DETAILS OF LEARNING ACTIVITIES AND TEACHING METHODS
Category Hours of study time Description
Scheduled Learning & Teaching activities 11 Lectures
Scheduled Learning & Teaching activities 11 Tutorials
Scheduled Learning & Teaching activities 11 Practicals
Guided Independent Study 117 Guided independent study

 

ASSESSMENT
FORMATIVE ASSESSMENT - for feedback and development purposes; does not count towards module grade
Form of Assessment Size of Assessment (e.g. duration/length) ILOs Assessed Feedback Method
Weekly exercise sheets 11 x 3 hours All Generic feedback and informal individual discussions
Computer- marked quizzes 6 x 30 minutes 1, 9, 10 Computer generated feedback
Project draft 5000 words 2-10 Written feedback

 

SUMMATIVE ASSESSMENT (% of credit)
Coursework 0 Written Exams 60 Practical Exams 40
DETAILS OF SUMMATIVE ASSESSMENT
Form of Assessment % of Credit Size of Assessment (e.g. duration/length) ILOs Assessed Feedback Method
Written exam - closed book 30 1.5 hours - Summer Exam Period 2, 3, 4, 5, 6, 7, 8, 9, 10 Generic Feedback
Practical - computer marked quizzes 40 (non-condonable) 6 x 30 minutes 1, 9, 10 Computer generated feedback
Project 30 5000 words 2-10 Written feedback

 

DETAILS OF RE-ASSESSMENT (where required by referral or deferral)
Original Form of Assessment Form of Re-assessment ILOs Re-assessed Time Scale for Re-assessment
Written exam Written exam (30%) 2, 3, 4, 5, 6, 7, 8, 9, 10 August Ref/Def period
Coursework - computer marked quizzes Coursework: computer marked quizzes (40% non-condonable) 1, 9, 10 Summer, with a deadline in August
Project Coursework: project (30%) 2-10 Summer, with a deadline in August

 

RE-ASSESSMENT NOTES

The referred and deferred assessment will be by examination, project and computer-marked quizzes. For referrals, only the computer marked quizzes will count, a mark of 40% being awarded if the quizzes are passed. For deferrals, candidates will be awarded the higher of the deferred and original mark for each of the quiz, project and exam  components.

RESOURCES
INDICATIVE LEARNING RESOURCES - The following list is offered as an indication of the type & level of
information that you are expected to consult. Further guidance will be provided by the Module Convener

Basic reading:

ELE: http://vle.exeter.ac.uk

 

Reading list for this module:

Type Author Title Edition Publisher Year ISBN Search
Set Jungnickel, D. Graphs, Networks and Algorithms Springer 1999 000-3-540-63760-5 [Library]
Set Ahuja, R.K., Magnanti, T.L. & Orlin, J.B. Network Flows: Theory, Algorithms, and Applications Prentice-Hall 1993 000-0-136-17549-X [Library]
Set Smith, D.K. Networks and Graphs: Techniques and Computational Methods Horwood Publishing 2003 000-1-898-56391-8 [Library]
CREDIT VALUE 15 ECTS VALUE 7.5
PRE-REQUISITE MODULES ECM2902
CO-REQUISITE MODULES
NQF LEVEL (FHEQ) 6 AVAILABLE AS DISTANCE LEARNING No
ORIGIN DATE Thursday 07 May 2015 LAST REVISION DATE Wednesday 18 January 2023
KEY WORDS SEARCH Graph; network; algorithm; mathematics; complexity.