DM582: Advanced Algorithms
The Study Board for Science
Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N330070102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Spring
Level: Bachelor
STADS ID (UVA): N330070101
ECTS value: 7.5
Date of Approval: 21-10-2025
Duration: 1 semester
Version: Archive
Entry requirements
Academic preconditions
Students taking the course are expected to
- have knowledge of basic algorithms and data structures as well as implementations of such in an imperative programming language, including stacks, queues, search trees, and priority queues, as well as sorting methods and basic graph algorithms (e.g., from DM578),
- have knowledge of algorithm design techniques and be able to analyze algorithms using asymptotic analysis and be able to compare asymptotic results (e.g., from DM578),
- be able to use basic mathematical argumentation, including logical expressions, proofs by induction and contradiction, and counting techniques (e.g., from DM549), and
- be able to use basic discrete probability theory (e.g, from AI501).
Course introduction
The aim of the course is to enable the student to use randomization and probabilistic methods in the design and analysis of algorithms and to familiarize the student with advanced algorithmic topics such as flows of networks and string matching, as well as generally-applicable techniques for establishing upper and lower bounds for the time complexity of algorithms, including amortized analysis.
Expected learning outcome
The learning objectives of the course are that the student demonstrates the ability to:
- Apply the topics on discrete probability theory to estimate the expected running time of algorithms
- Develop and analyze basic randomized algorithms
- Apply techniques from universal hashing to choose hash functions with good expected performance
- Formulate a flow-model for problems resembling those covered in the course
- Assess which string matching technique to apply for a given problem
- Apply techniques from the course to assess the amortized time complexity of operations on a data structure
- Establish lower bounds for the time complexity of algorithmic problems
Content
The following main topics are contained in the course:
- Randomized algorithms
- Probabilistic analysis of algorithms
- The probabilistic method
- Universal and perfect hashing
- Flows in networks
- String matching
- Amortized analysis
- Lower bounds
Literature
Examination regulations
Exam element a)
Timing
Spring and June
Tests
Portfolio with oral defense
EKA
N330070102
Assessment
Second examiner: External
Grading
7-point grading scale
Identification
Full name and SDU username
Language
Normally, the same as teaching language
Duration
Oral exam, 25 minutes
Examination aids
All common aids allowed
Oral exam: No aids allowed
ECTS value
7.5
Additional information
The portfolio exam consists of two elements:
- Multiple-choice test during the course
- Oral exam
Re-exam: Oral exam (identical to element 2 in the ordinary exam).
Indicative number of lessons
Teaching Method
Planned lessons:
Total number of planned lessons: 70
Hereof:
Common lessons in classroom/auditorium: 40
Team lessons in classroom: 30
Structurally, the scheduled sessions are used to introduce new material roughly half of the times and to discuss properties and variants related to the material during the other half. For the first part, we use a modified variant of a classic lecture, where foundational concepts and methods are presented theoretically as well as through examples on concrete data. Questions and discussions are encouraged. In the other half, work revolves around exercises and discussion topics related to the material introduced in the preceding lectures. During this, the students can work specifically with the more challenging topics. Also in this connection, questions that arise can be brought up.
Other planned teaching activities:
Solve assignments, read the assigned literature, practice applying acquired knowledge.