Module Details |
| The information contained in this module specification was correct at the time of publication but may be subject to change, either during the session because of unforeseen circumstances, or following review of the module at the end of the session. Queries about the module should be directed to the member of staff with responsibility for the module. |
| Title | NETWORKS IN THEORY AND PRACTICE | ||
| Code | MATH367 | ||
| Coordinator |
Dr P Buividovich Mathematical Sciences Pavel.Buividovich@liverpool.ac.uk |
||
| Year | CATS Level | Semester | CATS Value |
| Session 2025-26 | Level 6 FHEQ | Second Semester | 15 |
Aims |
|
|
•To develop an appreciation of network models for real world problems. •To describe optimisation methods to solve them. •To study a range of classical problems and techniques related to network models. |
|
Learning Outcomes |
|
|
(LO1) Apply basic concepts of graph theory to solve practical problems. |
|
|
(LO2) Analyse the computational complexity of optimisation algorithms based on their structure. |
|
|
(LO3) Apply optimization algorithms for graphs and networks to practical problems. |
|
|
(LO4) Interpret logistics and workflow optimisation problems in the language of (cost) flow networks and apply algorithms on flow networks to solve them. |
|
|
(LO5) Map real-world problems into an abstract mathematical description in terms of graphs and networks. |
|
|
(LO6) Distinguish between P- and NP-hard problems. Explain the mathematical origin of NP-hardness. Apply the branch & bound solution strategy to practical NP hard problems. |
|
|
(LO7) Analyse and prove correctness and complexity of algorithms on graphs and networks. |
|
Syllabus |
|
|
Basic graph and network definitions and results. Minimal spanningtrees. Shortest/path algorithms (Dijkstra, Floyd). Edge routing, Euler tours,Chinese postman problem. Node routing, Hamilton tours,.Travelling salesman problem. Complexity problems. Branch and bound strategies, integer linear programming, generalisedassignments. Lagrangean relaxation methods, knapsack problems, set-covering problems. Heuristics, local search methods, vehicle routing problem. |
|
Recommended Texts |
|
| Reading lists are managed at readinglists.liverpool.ac.uk. Click here to access the reading lists for this module. | |
Pre-requisites before taking this module (other modules and/or general educational/academic requirements): |
| MATH102 CALCULUS II 2023-24; MATH101 Calculus I 2022-23; MATH101 Calculus I 2023-24; MATH103 Introduction to Linear Algebra 2022-23; MATH103 Introduction to Linear Algebra 2023-24; MATH102 CALCULUS II 2022-23 |
Co-requisite modules: |
Modules for which this module is a pre-requisite: |
Programme(s) (including Year of Study) to which this module is available on a required basis: |
Programme(s) (including Year of Study) to which this module is available on an optional basis: |
Assessment |
||||||
| EXAM | Duration | Timing (Semester) |
% of final mark |
Resit/resubmission opportunity |
Penalty for late submission |
Notes |
| formal examination | 120 | 50 | ||||
| CONTINUOUS | Duration | Timing (Semester) |
% of final mark |
Resit/resubmission opportunity |
Penalty for late submission |
Notes |
| class test | 60 | 30 | ||||
| self-paced quizzes on CANVAS | 0 | 20 | ||||