Graphs, Networks and Algorithms - 2023 entry
MODULE TITLE | Graphs, Networks and Algorithms | CREDIT VALUE | 15 |
---|---|---|---|
MODULE CODE | ECM3906 | MODULE CONVENER | Dr Mark Callaway (Coordinator) |
DURATION: TERM | 1 | 2 | 3 |
---|---|---|---|
DURATION: WEEKS | 0 | 11 | 0 |
Number of Students Taking Module (anticipated) | 20 |
---|
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
On successful completion of this module you should be able to:
Module Specific Skills and Knowledge
Discipline Specific Skills and Knowledge
Personal and Key Transferable / Employment Skills and Knowledge
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.
Scheduled Learning & Teaching Activities | 33 | Guided Independent Study | 117 | Placement / Study Abroad | 0 |
---|
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 |
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 |
Coursework | 0 | Written Exams | 60 | Practical Exams | 40 |
---|
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 |
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 |
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.
information that you are expected to consult. Further guidance will be provided by the Module Convener
Basic reading:
Reading list for this module:
Type | Author | Title | Edition | Publisher | Year | ISBN |
---|---|---|---|---|---|---|
Set | Jungnickel, D. | Graphs, Networks and Algorithms | Springer | 1999 | 000-3-540-63760-5 | |
Set | Ahuja, R.K., Magnanti, T.L. & Orlin, J.B. | Network Flows: Theory, Algorithms, and Applications | Prentice-Hall | 1993 | 000-0-136-17549-X | |
Set | Smith, D.K. | Networks and Graphs: Techniques and Computational Methods | Horwood Publishing | 2003 | 000-1-898-56391-8 |
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 7th May 2015 | LAST REVISION DATE | Wednesday 18th January 2023 |
KEY WORDS SEARCH | Graph; network; algorithm; mathematics; complexity. |
---|
Please note that all modules are subject to change, please get in touch if you have any questions about this module.