To path indicator Subpages of “Teaching“ To navigation To quick access To footer with other services
To content
Algorithm Engineering
Fakultät für Informatik
Students in summer on north campus, red gears in background. © Roland Baege​/​TU Dortmund

Courses given by Algorithm Engineering

Summer 2025

Algorithmic Geometry
Data Structures, Algorithms and Programming 2

Regularly offered courses

Bachelor

Description

In the lecture "Data Structures, Algorithms and Programming 2" (DAP 2) we deal with techniques for designing and analyzing algorithms and data structures.

In this course you will learn to:
  • Describe basic algorithms and data structures, apply them to small examples and adapt them to new problems
  • Determine, compare and mathematically prove properties such as the runtime and correctness of       algorithms
  • Develop new algorithms and data structures using basic design methods
Examples for basic algorithms:
  • Algorithms for sorting numbers such as MergeSort, InsertionSort, Quicksort, Heapsort, CountingSort and RadixSort and algorithms for the selection problem
  • Algorithms for basic organization problems such as the knapsack problem
  • Graph algorithms such as breadth-first search, depth-first search, topological sorting, minimum    spanning trees and shortest paths
Examples for basic data structures:
  • Heaps
  • Hash charts
  • Balanced binary search trees such as red-black trees
  • Graph representations such as adjacency lists and adjacency matrices

For many algorithmic problems it is necessary to adapt these basic algorithms and data structures or to   develop new algorithms and data structures. In the lecture we will learn about design techniques such as divide-and-conquer, icremental algorithms, greedy algorithms and dynamic programming.

To analyze the runtime of algorithms, we learn about O-notation. To analyze the runtime of recursive algorithms, the recurrence for the runtime must be determined and solved using techniques such as recursion trees or the master theorem. We also learn various techniques such as loop invariants to show the correctness of algorithms.

Description

The basic techniques introduced in DAP 2 are deepened and applied to more complex problems, in addition to selected problems with large application areas, advanced aspects such as approximation and advanced design methods.

Topics include:
  • Hashing methods, string matching
  • Graph algorithms, e.g. strong connection in graphs, maximum matchings, network flow problems,     cutting problems (min-cut and max-flow), traveling salesperson problem, vertex cover, maxSAT
  • Advanced data structures, e.g. B-trees, data structures for disjoint sets, augmentation of data              structures
  • Analysis techniques, e.g. amortized analysis of algorithms, analysis of randomized algorithms
  • Optimization techniques, e.g. linear programming, approximation quality and schemes
Literature
  • Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (also available at the university library as an e-book in English and German)
  • Additional literature references and scripts will be made available on Moodle
Examination
  • Coursework: successful participation (50 % of the points) in the weekly Moodle quizzes
  • For Bachelor students of Computer Science and Applied Computer Science: written exam, 90 minutes, 2 dates
  • Students of other disciplines have either oral or written exams. The exact requirements will be                 announced in the lecture (see slides). In case of a written exam, it will take place at the same time as the exams above. Please note the registration deadlines for examinations at the examinations office, which are very early for written exams (usually 2 weeks in advance).
Description

Competitive programming is about developing algorithmic solutions for specific problems and implementing them in the shortest possible time. In this course, students deepen their understanding of basic efficient      algorithms and practise applying the algorithms and programming under time pressure. Since 1970, the Association for Computing Machinery (ACM) has organized the annual International Collegiate Programming Contest (ICOC), which we will use as a guide.

In our project, important algorithms and data structures for solving problems from previous years of the ICPC are presented in lectures and approaches to solutions are discussed. In addition to the lectures, tasks are solved and programmed in a simulated competition situation in teams of 3. At the end of the semester, participants will take part in the Winter Contest or GCPC.

Timetable and process

The specialized project takes place every Wednesday from 12 to 4 pm. The first two hours deal with specific techniques for solving competition problems. The last two hours are dedicated to working on exercises.

Programming language: C, C++, Java or Python (you need to find two other participants for your preferred language)

Course language is German, but the problem descriptions / assignments will be in English!

Prerequisites
  • Programming skills (internships DAP 1 and 2)
  • Data Structures, Algorithms and Programming 2
  • Basic knowledge in the following areas:
    • Algorithm design methods: greedy, divide and conquer, dynamic programming, backtracking and recursion
    • Basic data structures: arrays, lists, stacks, queues, binary search trees, heaps, adjacency lists and matrices
    • Standard algorithmic topics: O-notation, sorting, searching, hashing, simple graph algorithms (e.g. tree traversal, breadth-first and depth-first search)
  • Basic knowledge of matching and flow algorithms (EA) is helpful, but not necessary
Examination

All final module examinations are carried out in teams of 3

  • 30 min presentation on a data structure or programming paradigm as well as guiding the participants to solve the corresponding task types
  • 3 out of 5 of the weekly problems per task type solved
  • Successful participation in the internal programming challenge
Materials
Description

Competitive programming is about developing algorithmic solutions for specific problems and implementing them in the shortest possible time. Since 1970, the Association for Computing Machinery (ACM) has organized the annual International Collegiate Programming Contest (ICOC), which we will use as a guide.

In our seminar, advanced algorithms and data structures for solving problems from previous years of the ICPC are presented and approaches to solutions are discussed.

Prerequisites

This course ties to the specialized project "Algorithms for Competitve Programming". Previous know-ledge from this course is desirable, but not necessary. You can also take the specialized project simultaneously (Wednesday morning: seminar, Wednesday afternoon: project).

We expect basic knowledge of algorithm design methods (e.g. dynamic programming, backtracking), data structures (e.g. queues, binary search trees, heaps, graphs) and standard algorithmic topics (O-notation, sorting, searching, hashing).

Master

Description

The lecture "Algorithms and Data Structures" with the accompanying exercise provides the basis for most of the more advanced special lectures in the field of algorithmic and formal foundations, and also deals with more advanced and complex algorithms and data structures.

The lecture focuses on approximation algorithms and linear optimization. In addition to these topics, various advanced algorithmic topics are covered, such as parameterized algorithms and advanced data structures.

There are many algorithmic problems for which we cannot expect to find efficient algorithms. In order to find solutions to such problems, approximation algorithms are of central importance. Approximation algorithms calculate a solution that is not necessarily optimal, but for which we can give a quality guarantee. For example, Christofide's algorithm for the round trip problem (TSP) calculates a tour that is at most 1.5 times as long as the optimal tour in the worst case. We learn about different approximation algorithms and techniques for the design of approximation algorithms.

Linear optimization together with integer optimization can be used to solve a variety of optimization, which are essential for computer science. Linear optimization plays a particularly important role in approximation algorithms and we will take a closer look at this application of linear optimization in the lecture.

Description

Geometric algorithms comprise the design and analysis of algorithms and data structures for geometric problems. In the lecture, some basic problems are considered first: Computing the convex hull of a set of points, the intersection points of a set of lines, or a triangulation of a simple polygon. We then look at algorithms for calculating known geometric structures, such as Voronoi diagrams, Delaunay triangulations and arrangements. We also look at data structures for efficient queries on geometric data, such as range trees, kd-trees and quadtrees. Three main types of algorithms are used: incremental, divide-and-conquer, and sweep. Some of these occur as randomized algorithms.

Prerequisites

Previous knowledge of the lecture "Algorithms and Data Structures" or comparable knowledge is expected.

Examination
  • Coursework: active participation (incl. presentation of your own solutions)
  • Oral exam
Description

In this seminar we will deal with current research topics of the Algorithm Engineering research group based on selected recent publications in the field of algorithms. The group conducts research on a wide range of algorithmic topics, in particular geometric algorithms and data structures, algorithm engineering, geometric networks and algorithms for geoinformation systems.

Prerequisites

Previous knowledge of the lectures "Algorithms and Data Structures" or "Geometric Algorithms" or comparable knowledge is expected.

*Alternating with the research group Efficient Algorithms and Complexity Theory

Past Terms

Seminar on Algorithms
Algorithms and Data Structures
Proseminar: Advanced Algorithms for Competitive Programming
Specialized Project: Algorithms for Competitive Programming
Algorithmic Geometry
  • Lecturer: Kevin Buchin
  • Module: Algorithmische Geometrie (Master INF-MSc-602 (Informatik, Angewandte Informatik))
  • Type: 2 SWS lecture + 2 SWS exercise
Data Structures, Algorithms and Programming 2
Seminar of Algorithm Engineering research group
Algorithms and Data Structures
Proseminar: Advanced Algorithms for Competitive Programming
Proseminar: Algorithms for Packing Problems
Specialized Project: Algorithms for Competitive Programming
  • Lecturer: Mart Hagedoorn
  • Module: Fachprojekt - Bachelor Informatik/Angewandte Informatik
  • Type: 4 SWS project
Algorithmic Geometry
  • Lecturer: Kevin Buchin
  • Module: Algorithmische Geometrie (Master INF-MSc-602 (Informatik, Angewandte Informatik))
  • Type: 2 SWS lecture + 2 SWS exercise
Efficient Algorithms
Specialized Project: Algorithms for Competitive Programming
  • Lecturer: Mart Hagedoorn
  • Module: Fachprojekt - Bachelor Informatik/Angewandte Informatik
Specialized Project: Algorithms for Competitive Programming
Proseminar: Allocation and Assignment Algorithms
Seminar: Algorithm Engineering
To top of page