DM582 - Advanced Algorithms
 
Spring 2025
Kim Skak Larsen

Home

Lectures and Exercises

Due to integration with the platform "itslearning", this page is organized into topics, which are sorted according to the date of the first lecture of the topic and the later exercises are placed under the topic they belong to. Thus, if one looks at all the dates of lectures and exercises, one will not find an ordered list.

The entries are not static - announced material for a lecture may be updated to what was actually covered after the lecture was given. At the end of the course, the lecture and exercises announcements on this page will reflect exactly what was covered.

Some lectures have slides or code examples that can be found on the literature page.

Date Time Place Event
Introduction. Network Flows.
3/2 8-10 U43 Lecture
11/2 (H9), 12/2 (H8) 10-12 (H9), 10-12 (H8) U51 (H9), U24 (H8) Exercises
On Discrete Probability Theory.
6/2 10-12 U23 Lecture
13/2 (H9), 14/2 (H8) 12-14 (H9), 8-10 (H8) U20 (H9), U42 (H8) Exercises
Network Flows: Edmonds-Karp and Examples.
10/2 8-10 U43 Lecture
20/2 (H9), 21/2 (H8) 10-12 (H9), 12-14 (H8) U43 (H9), U156 (H8) Exercises
Randomized Algorithms: Contention Resolution, Global Minimum Cut.
18/2 10-12 U42 Lecture
26/2 10-12 (H8), 12-14 (H9) U20 (H8), U51 (H9) Exercises
Randomized Algorithms: Waiting Times, MAX 3-SAT Approximation.
19/2 12-14 U20 Lecture
27/2 (H9), 28/2 (H8) 12-14 (H9), 12-14 (H8) U21 (H9), U50A (H8) Exercises
Randomized Quicksort and Selection.
25/2 10-12 U42 Lecture
6/3 (H9), 7/3 (H8) 10-12 (H9), 12-14 (H8) U42 (H9), U43 (H8) Exercises
Amortized Analysis: Stack, Counter, Dynamic Tables.
4/3 10-12 U23 Lecture
13/3 (H9), 14/3 (H8) 12-14 (H9), 12-14 (H8) U42 (H9), U43 (H8) Exercises
20/3 (H9), 21/3 (H8) 10-12 (H9), 12-14 (H8) U50A (H9), U154 (H8) Exercises
Universal and Perfect Hashing.
11/3 12-14 U43 Lecture
String Matching: Naive, Rabin-Karp, Finite Automata.
18/3 12-14 U43 Lecture
27/3 (H9), 28/3 (H8) 12-14 (H9), 12-14 (H8) U20 (H9), U154 (H8) Exercises
String Matching: Finite Automata, Knuth-Morris-Pratt.
24/3 12-14 U43 Lecture
3/4 12-14 U20 Exercises
Online Algorithms.
2/4 12-14 U43 Lecture
10/4 12-14 U50A Exercises
Deterministic Selection. Adversarial Lower Bound Techniques.
7/4 12-14 U43 Lecture
24/4 10-12 U43 Exercises
Meldable Priority Queues. Evaluation. Exam Information.
23/4 8-10 U43 Lecture
26/5 12-14 U21 Exercises

 


   Data protection at SDUDatabeskyttelse på SDU