COMP30870 Graph Algorithms

Academic Year 2020/2021

This module is an introduction to basic graph algorithms. It will cover:
1. Modelling industry and scientific problems in terms of graphs
2. Graph Traversal Algorithms: Breadth-First search, Depth-First search, Topological ordering
3. Path-based Optimisation: Shortest paths, All-pair shortest paths
4. Connectivity Problems: Minimum spanning trees, Connected components, Strongly connected components
5. Approximation Algorithms: Vertex cover, Travelling salesman problem
6. Network Analysis: Centrality computation (e.g., PageRank)

Show/hide contentOpenClose All

Curricular information is subject to change

Learning Outcomes:

On completion of this module, students will be able to:
1. Model real-world problems in terms of graphs
2. Understand the basic graph algorithms
3. Be able to mathematically analyse simple graph algorithms
4. Competently apply the basic graph algorithms to solve problems in various domains

Indicative Module Content:

This module is an introduction to basic graph algorithms. It will cover:
1. Modelling industry and scientific problems in terms of graphs
2. Graph Traversal Algorithms: Breadth-First search, Depth-First search, Topological ordering
3. Path-based Optimisation: Shortest paths, All-pair shortest paths
4. Connectivity Problems: Minimum spanning trees, Connected components, Strongly connected components
5. Approximation Algorithms: Vertex cover, Travelling salesman problem
6. Network Analysis: Centrality computation (e.g., PageRank)

Student Effort Hours: 
Student Effort Type Hours
Lectures

20
Tutorial

22
Autonomous Student Learning

90
Total

132
Approaches to Teaching and Learning:
Threshold Concepts; Problem-based Learning; Continuous assessment; Lectures; Regular Assignments 
Requirements, Exclusions and Recommendations

Not applicable to this module.


Module Requisites and Incompatibles
Pre-requisite:
COMP20280 - Data Structures, COMP20290 - Algorithms


 
Assessment Strategy  
Description Timing Open Book Exam Component Scale Must Pass Component % of Final Grade
Assignment: The assignment will involve modelling real-world problems in terms of graphs, designing algorithms, proving correctness and analysing the algorithms mathematically. Throughout the Trimester n/a Graded No

30
Assignment: This assignment will involve designing algorithms and mathematically analysing it. In addition, it may involve one problem-based learning exercise possibly involving some programming. Throughout the Trimester n/a Graded No

50
Multiple Choice Questionnaire: There will be a few MCQ style questions on Brightspace to assess the level of understanding. These can be held during the practice sessions and/or the lectures and in some cases, outside these hours. Throughout the Trimester n/a Graded No

20

Carry forward of passed components
No
 
Resit In Terminal Exam
Autumn No
Please see Student Jargon Buster for more information about remediation types and timing. 
Feedback Strategy/Strategies

• Feedback individually to students, post-assessment

How will my Feedback be Delivered?

Not yet recorded.

1. "Introduction to Algorithms", 3rd Edition (The MIT Press) by Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein
2. "Algorithm Design" by Jon Kleinberg and Éva Tardos
3. "Algorithms" 4th edition by Robert Sedgewick and Kevin Wayne