DM829: Efficient graph algorithms (5 ECTS)

STADS: 15011401

Level
Master's level course

Teaching period

The course is offered when needed.

Teacher responsible
Email: cwn@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal. 3. kvartal

Prerequisites:
None

Academic preconditions:
asic knowledge of algorithms and probability, obtained e.g. from DM507 Algorithms and Data Structures, DM508 Algorithms and Complexity, and DM528 Combinatorics, Probability, and Randomized Algorithms.

Course introduction
The purpose of the course is to give the student detailed knowledge of graph algorithms with small time and/or space complexity as well as compact graph representations relating to length minimization, with primary focus on shortest paths. Classical algorithms such as Dijkstra are too slow for many applications like GPS and communication networks, and these algorithms require the whole graph to be stored in memory. In practice, approximate shortest path distances often suffice. New preprocessing techniques and graph representations allow such distance queries to be answered much faster and with less memory usage.

Expected learning outcome
At the end of the course the student is expected to be able to:

• give an account of efficient algorithms and graph representations for the graph problems covered in the course,
• identify the overall methods and algorithmic ideas covered in the course,
• apply methods and algorithmic ideas covered in the course to new problems similar in nature to those from the course.

Subject overview
Shortest paths, distance oracles, spanners, multiplicative and additive distance approximations, minimum spanning trees.

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
a) Mandatory assignments, an oral presentation of an article and a project assignment are evaluated collectively. Pass/fail, internal evaluation by the teacher.

Re-examination according to the rules approved by the Study Board.
The re-exam may differ from the ordinary exam.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger: 24 timer
Eksaminatorietimer/opgaveregning: 14 timer
Educational activities

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.