Explore UCD

UCD Home >

COMP30870

Academic Year 2024/2025

Graph Algorithms (COMP30870)

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

Curricular information is subject to change.

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

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. 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

Student Effort Hours:
Student Effort Type Hours
Autonomous Student Learning

90

Lectures

20

Tutorial

22

Total

132


Approaches to Teaching and Learning:
Threshold Concepts; Problem-based Learning; Learning by designing wrong algorithms first; Continuous assessment; Lectures; Tutorial exercises for practice; 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 Component Scale Must Pass Component % of Final Grade In Module Component Repeat Offered
Assignment(Including Essay): This assignment will involve questions related to designing algorithms, proving correctness and mathematically analysing their running time. Week 6, Week 7 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. Week 9 Alternative linear conversion grade scale 40% No
50
No

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
4. "Algorithms Illuminated" by Tim Roughgarden
5. "The Algorithm Design Manual" by Steven Skiena

Name Role
Mr Ryan O'Connor Tutor

Timetabling information is displayed only for guidance purposes, relates to the current Academic Year only and is subject to change.
Spring Exam Mid-term (ALU) Offering 1 Week(s) - 28 Fri 16:00 - 18:50
Spring Lecture Offering 1 Week(s) - 20, 21, 22, 23, 24, 25 Tues 10:00 - 11:50
Spring Lecture Offering 1 Week(s) - 20, 21, 22, 23, 24, 25 Wed 10:00 - 10:50
Spring Tutorial Offering 1 Week(s) - 20, 21, 22, 23, 24, 25 Wed 11:00 - 12:50
Spring Tutorial Offering 1 Week(s) - 20, 21, 22, 23, 24, 25 Wed 14:00 - 15:50