Explore UCD

UCD Home >

COMP30870

Academic Year 2026/2027

Graph Algorithms (COMP30870)

Subject:
Computer Science
College:
Science
School:
Computer Science
Level:
3 (Degree)
Credits:
5
Module Coordinator:
Dr Mark Meng
Trimester:
Autumn
Mode of Delivery:
On Campus
Internship Module:
No
How will I be graded?
Letter grades

Curricular information is subject to change.

This module introduces 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. Optimisation: Shortest paths, All-pair shortest paths, Maximum flow, etc.
4. Connectivity Problems: Minimum spanning trees, Connected components, Strongly connected components
5. Approximation Algorithms: Vertex cover, Travelling salesman problem, etc.

About this Module

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 and the algorithm design process
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. Optimisation: Shortest paths, All-pair shortest paths, Maximum flow, etc.
4. Connectivity Problems: Minimum spanning trees, Connected components, Strongly connected components
5. Approximation Algorithms: Vertex cover, Travelling salesman problem, etc.

The United Nations identified seventeen Sustainable Development Goals (SDGs) as core to the 2030 Agenda for Sustainable Development, and UCD contributes in general to SDG 4 Quality Education. Further SDGs explored within this module if relevant are listed below. A scale of 1 - 5 indicates the extent to which the SDG is covered.


 

Student Effort Hours:
Student Effort Type Hours
Autonomous Student Learning

72
Lectures

24
Tutorial

24
Total

120

Approaches to Teaching and Learning:
Problem-based Learning; Proof and Analysis; In-Class Demonstration; Continuous Assessment; Lectures; Tutorial Exercises

Requirements, Exclusions and Recommendations

Not applicable to this module.


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


 

Assessment Strategy
Description Timing Component Scale Must Pass Component % of Final Grade Component repeat (in-module) Offered
Exam (Open Book): Exam to assess if a student can model a real-world problem into a graph problem, use a learned algorithm to solve the problem, and analyse the correctness and time complexity of the proposed solution. Week 6 Alternative linear conversion grade scale 40% No
50
 No
Exam (In-person): A final exam consisting of algorithm design and analysis questions as well as short MCQ questions. End of trimester
Duration:
2 hr(s)
 Alternative linear conversion grade scale 40% No
50
 No

As part of UCD's student support, under the Additional Consideration policy, extensions may be available for the following assessments in the module: Assignment (including essay/poster), Portfolio, Reflective Assignment, Report(s), and Individual Project.


Carry forward of passed components
No
 

Resit In Terminal Exam
Spring Yes - 2 Hour
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
4. "Algorithms Illuminated" by Tim Roughgarden
5. "The Algorithm Design Manual" by Steven Skiena

Name Role
Ms Vaaibhavi Singh Tutor

Timetabling information is displayed only for guidance purposes, relates to the current Academic Year only and is subject to change.
Autumn Lecture Offering 1 Week(s) - Autumn: All Weeks Thurs 12:00 - 12:50
Autumn Lecture Offering 1 Week(s) - Autumn: All Weeks Wed 09:00 - 09:50
Autumn Tutorial Offering 1 Week(s) - 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12 Mon 10:00 - 11:50
Autumn Tutorial Offering 2 Week(s) - Autumn: All Weeks Thurs 14:00 - 15:50
Print this page
Fill in the following details:
Enter the body of your query here.

From time to time UCD would like to send you further information that we feel, based on your enquiry, would be of interest to you.