Algorithms is a focus area at SDU, with an unusually large and strong research group with more than 9 researchers and a large variety of courses in the area.
In addition to offering expertise in concrete application areas, a solid background in algorithms makes it easy to enter other subareas of computer science. In a fast-moving field such as computer science, the ability to adapt to ever-changing circumstances is important for a successful career.
Most of our algorithms courses relate to the following:
- Organisation of large datasets, facilitating fast searching and computation: Searching and efficient computation is the essence: String Algorithms lays the foundations for technologies enabling Google's fast searches, Parallel Computing explains algorithms for utilising large computer clusters, I/O-Efficient Algorithms and Data Structures provides efficient methods for dealing with Big Data, and GPS route planning starts with Computational Geometry.
- Resource optimisation: The application areas are numerous and many different techniques must be employed. Generally-applicable methods and models are introduced in Linear and Integer Programming and Heuristics and Constraint Programming for Discrete Optimization, while more specialised or topic-related ideas are developed in Online Algorithms, Combinatorial Optimisation, Scheduling Timetabling and Routing, Network Programming, and Satisfiability.
- Area-specific algorithms and applications: Sometimes necessary techniques from many different topics need to be pooled to address issues in one domain. Examples include Algorithms in Cheminformatics, Computer Game Programming, and Cryptology.
In the academic year 2021/2022, we will be offering the following courses within the area of algorithms:
The development of an algorithm with optimal time complexity often depends on the design of a data structure with just the right properties. Likewise, the choice or design of an efficient data structure often makes the difference between a large program which is too slow, and one that meets the user demands.
The purpose of this course is to give you a thorough understanding of advanced data structures such that later you will be able to use them when approaching complex problem solving and programming.
Responsible teacher: Kim Skak Larsem
This course enables you to solve non-trivial discrete computational problems by applying advanced algorithmic ideas, graph theoretical approaches, discrete mathematics and complexity theory to problems motivated from or arising in chemistry.
The course gives an academic basis for writing a Master's thesis that aims to apply core Computer Science approaches to questions in Chemistry, Biology, Physics, or Mathematics.
Responsible teacher: Daniel Merkle
This course provides an introduction to the science of Discrete Optimization and focuses on two of its solution paradigms: Constraint Programming and Optimization Heuristics and Metaheuristics.
Constraint Programming tries to solve problems by modelling them by means of a declarative programming language and then using standard deduction rules, similar to logic reasoning, to reduce the space where solutions are searched.
Optimization Heuristics and Metaheuristics are general principles to find near-optimal solutions. They are the last resort in case a problem turns out to be computationally too difficult to be solved exactly. They are often inspired by nature. For example, local search techniques are based on the principle of trial and error, which is a possible way in which the humans solve problems.
To be successful the general principles must be adapted to the specific problem exploiting its structure and efficient implementations. Hence, the course includes first-hand experience through programming assignments.
Responsible teacher: Marco Chiarandini
Cryptology is the creation of secret codes, the possibilities for breaking them, and cryptographic protocols for security. Number-theoretic problems relevant to cryptology and the basic algebra necessary to understand them will also be presented during the course.
Cryptology has many applications, including sending private messages, enabling commerce over the internet (through encryption of credit card numbers, electronic money, secure methods for electronic signatures on documents, etc.), and authentication such as PIN codes for credit cards and logins.
Academic preconditions: Students taking this course are expected to have knowledge of linear algebra and either complexity theory or group theory.
Responsible teacher: Joan Boyar
This course teaches you how to apply theory and methods from combinatorial optimisation to reason about problems of a combinatorial nature and to develop efficient algorithms for solving practical problems which are similar in nature to those studied in the course.
You will be able to argue that a combinatorial optimisation problem is NP-hard and suggest methods for obtaining approximate solutions via methods learned in the course.
Responsible teacher: Jørgen Bang-Jensen
Linear and Integer programming deals with finding mathematically provable optimal solutions to resource constrained optimisation problems. These problems arise in all contexts of decision making, such as manufacturing, logistics, health care, education, finance, energy supply, and many others.
The course focuses on the basics of linear optimisation and duality theory and on the main solution techniques: the simplex method, branch and bound, and cutting planes.
It aims at enabling you with the skills to model mathematically practical optimisation problems and to work with a mathematical software system for finding numerical solutions to the applications proposed.
Academic preconditions: Students taking the course are expected to have knowledge of linear algebra.
Responsible teacher: Marco Chiarandini
The course focuses on advanced solution techniques for solving challenging mathematical optimisation problems. We start from a few concrete applications taken from scheduling and vehicle routing and model them in terms of mixed integer linear programming (MILP) problems.
Due to the size of the instances of these problems in practical applications, basic solution techniques for MILP problems are insufficient and advanced solution techniques are required. These are: Lagrangian relaxation, Dantzig Wolfe decomposition, column generation, and Benders decomposition.
We study the theory and we practice with implementations.
Academic preconditions: Students taking the course are expected to have knowledge of Linear and Integer Programming, for example from the DM871 course.
Responsible teacher: Marco Chiarandini
Cryptography provides algorithms that are crucial for the security (e.g. confidentiality, integrity, and authenticity) of our modern communication.
However, these algorithms themselves are only one pillar for security; it is also important to implement these algorithms efficiently and securely. This course explains how to achieve high performance even for small embedded devices when implementing cryptographic (i.e. mathematical) algorithms and how to protect an implementation against side-channel attacks that are not looking for weaknesses in the algorithm or the implementation but in the physical properties of the computing platform.
The course is accompanied by hands-on tutorials on efficient implementation, side-channel analysis, and countermeasures.
Academic preconditions: Students taking this course are expected to have knowledge of basic cryptography, as covered in the course DM557: Network and Security.
Responsible teacher: Ruben Niederhagen
The course first introduces basic topics Graph Theory before quickly moving on to more advanced topics within this area.
Topics on both undirected and directed graphs are covered, as well as both algorithmic and theoretical results.
Many of the most known/useful results within Graph Theory will be covered in the course.
Responsible teacher: Anders Yeo
All courses require knowledge of algorithms and data structures, as well as basic discrete mathematics. Some courses have further academic preconditions. Please see the individual course descriptions.
As elective specialisation courses we recommend that you take either DM871 and DM872 or DM8xx: Cryptographic Engineering.
Master's Thesis projects
The following are examples of previous Master 'sThesis topics within the area of Algorithms:
- European football placement problems - complexities and exact solutions
- On-line graph colouring
- Aircraft routing
- Lattice-based cryptography
- Nearest neighbour search in high-dimensional spaces
- Theoretical aspects of computer-aided chemical synthesis design
Who teaches Algorithms?
Jørgen Bang-Jensen is an expert on graph theory. His main contributions to science come from his good nose for finding the right question to ask. This has led to many discoveries, lots of international collaborations, and has formed the basis of several PhD theses around the world. He always enjoys collaborating with external partners, where he can use his problem-solving skills to identify the core of the problem the company wants solved.
Joan Boyar enjoys general theoretical research, such as trying to understand the nature of online problems, but she also has a patent related to her work on small circuits for cryptographic functions. Her courses in online algorithms and cryptology usually include some of her own research.
Marco Chiarandini is fascinated by the fantastic journey that optimizers undertake to solve timetabling, scheduling and routing problems. The journey moves forward in the abstract world through problem communication, mathematical representation, algorithm design, implementation and experimental analysis. Finally, it returns to the real world with numbers that correspond to actually practicable decisions that yield systemic improvements and can ultimately ameliorate our lives.
Rolf Fagerberg is developing better algorithms and data structures for big data sets. He loves when smart algorithmic ideas and beautiful proofs come together to improve state-of-the-art development. He also enjoys when mathematical models and algorithmic ideas have real impact in applications, such as cheminformatics and game programming.
Lene Favrholdt likes to get to the core of an algorithmic problem. She strives to understand the essence of what results can be obtained, looking for precise and intuitive explanations of how and why they can (or cannot) be obtained. She finds communicating this understanding to colleagues and students in a clear and intuitive way very satisfying.
Kim Skak Larsen situates himself where theory meets practice. He appreciates efficient algorithms and competitive solutions as forming the foundation for implementation of large-scale systems while simultaneously being provably correct and effective. He meets his objectives on efficiency via his focus on data structures and database systems, and his goals on competitiveness through online and approximation algorithms.
Daniel Merkle is an interdisciplinary researcher who is fascinated when he sees the beauty of algorithmic ideas and formal methods. Using advanced methods from graph theory, optimization, parallel computing, and algorithmic engineering, he bridges the gap between theory and practice, solving highly relevant real-world problems arising in chemistry. He collaborates both with other university researchers and with large chemical companies.
Ruben Niederhagen is a computer scientist specialising in Post-Quantum Cryptography, Applied Cryptography, and Embedded Security, focusing on the efficient and secure implementation of cryptographic and cryptanalytic algorithms in software and in hardware.
Anders Yeo is an expert on Graph Theory (directed graphs, undirected graphs, hypergraphs, etc.) and algorithms (polynomial algorithms, NP-hardness, Fixed parameter tractibility, graph algorithms, etc.). He loves solving both theoretical and practical problems and has a large network of over 80 co-authors. His co-authors and other collaborators are situated around the world and cover a wide area of interests and research topics.