German website

study programs: Master of Computer Science (M_Inf), Data Science & Artificial Intelligence (M_DSAI), IT Engineering (M_ITE)

ECTS credits: 5

lecture term: summer semester

prerequesites: qualified bachelor program in computer science (or related), no prerequesite of master courses

language: English

For each lecture week, assignments are given on the handout server. These assignments serve as an exercise for the final exam. Some of them are eligible to be solved in a written way. Such solutions may be submitted to the lecturer who will comment them.

Algorithmics is the basis for creating correct and efficient software solutions. Although this lecture is self-contained, it is assumed that participants have already seen algorithms for fundamental problems like searching, sorting and elementary graph problems in their bachelor programme. At FH Wedel, this is done in the courses Programming, Discrete Mathematics, Algorithms and Data Structures. The focus of the bachelor courses is on technical realization. Some elementary proofs have also been covered. Time and space complexity has been addressed, but not systematically proved.

This lecture gives a more detailed insight into the world of algorithmics. We will abstract from technical details and put more emphasis on correctness and complexity. Traditionally, the focus of algorithmics is on complexity, especially on asymptotic time complexity. However, from time to time we will also prove the correctness of algorithms with mathematical methods.

There is another lecture of our master programme titled Computability and Complexity which gives a thorough theoretical base for algorithmics. However, it is not necessary for the comprehension of this lecture In some textbooks, computability and complexity is considered as part of algorithmics, but in even more textbooks, it is considered as part of automata theory.

Most of the research groups on Theoretical Computer Science work in algorithmics or in specification and verification. Therefore there are a lot of future dissertation themes pending in these areas. This gives a good chance for corresponding master themes which can be written at FH Wedel under my supervision. I have myself obtained my PhD in algorithmics with a strong focus on complexity, more precisely in computational geometry. I am in close contact with my former department at FU Berlin which is specialized in the field of algorithmics.

After repeating and formalizing the above-mentioned basic topics from bachelor study, we will address additional sorting and searching algorithms. Also advanced search tree methods and graph algorithms are addressed. Finally, we focus on selected topics of computational geometry with a special focus on the efficient computation of Voronoi diagrams and their applications.

For students enrolled at FH Wedel further teaching documents are given on the handout server. This also includes exercises which will be discussed in class.

All slides are given in English.

1. Introduction into formal algorithmics
     1.1 Comparing basic sorting techniques
     1.2 Complexity measures for the analysis of algorithms
     1.3 Lower bound for algorithms using comparisons only

2. Advanced searching and sorting
     2.1 Order statistics
     2.2 Searching in sorted arrays
     2.3 Sorting in finite domains

4. Graph algorithms
     4.1 Minimum spanning trees as motivation for basic algorithms
     4.2 Shortest paths (Dijkstra, Floyd-Warshall, Strassen)

     4.3 Computation of maximum flows in s/t-networks (Ford-Fulkerson, Edmonds-Karp, Dinic)
     4.4 Computation of graph matchings (bipartite, Edmonds)

5. String matching

6. Fundamentals of computational geometry
     6.1 Basic problems and the use of Voronoi diagrams for solving them (updated 2022-06-28)
     6.2 Sweep techniques (including computation of Voronoi diagrams) (updated 2022-07-05)

The text books for this lecture are the books of Cormen et al. Klein, and Turau. They are covered only in parts.

The books of Knuth and Sedgewick serve to broaden and improve the knowledge in selected topics. The book of Levitin serves as an introduction which is more suitable for the bachelor level, but still covers material relevant for this course.

The book of deBerg et al. also covers latest results in computational geometry which have been out of the scope of this lecture so far. But it serves also as an English reference for the content of chapter 6 which is taken from the German book of Klein originally. 

The book of Papadimitriou and Steiglitz covers graph algorithms much more detailed than this lecture. It is the only of the cited references describing the matching algorithm of Edmonds for arbitrary graphs.

The a bit older books of Preparata and Edelsbrunner serve as a reference for fundamentals and a lot of algorithms to discussed problems which are not directly addressed in this lecture though.

Mark de Berg / Otfried Cheong / Marc van Kreveld / Mark Overmars: Computational Geometry, Algorithms and Applications Springer 2008 (3. Aufl.), ISBN 978-3-540-77973-5

Thomas Cormen, Charles Leiserson / Ronald Rivest / Clifford Stein: Introduction to Algorithms, MIT Press 2001 (2nd ed.), ISBN 978-0262032933

Herbert Edelsbrunner: Algorithms in Combinatorial Geometry, Springer 1987, ISBN 3-540-13722-X

Rolf Klein: Algorithmische Geometrie, Springer 2005 (2. Aufl.), ISBN 978-3-540-20956-0

Franco Preparata / Michael Shamos: Computational Geometry - An Introduction, Springer 1988 (2. Auflage), ISBN 3-540-96131-3

Rolf Klein: Algorithmische Geometrie (in German), Springer 2005 (2. Aufl.), ISBN 978-3-540-20956-0

Donald Knuth: The Art of Computer Programming, vol. 1,2,3,
Addison Wesley 1997, ISBN 0-201-89683-4,  0-201-89684-2, 0-201-89685-0

Anany Levitin: Introduction to the Design and Analysis of Algorithms, Addison-Wesley 2006, ISBN 0-321-36413-9

Kurt Mehlhorn / Peter Sanders: Algorithms and Data Structures - The Basic Toolbox, Springer2008, ISBN 978-3-540-77977-3

Christos Papadimitriou / Kenneth Steiglitz: Combinatorial Optimization - Algorithms and Complexity, Dover 1998, ISBN 0-486-40258-4

Franco Preparata / Michael Shamos: Computational Geometry - An Introduction, Springer 1988 (2nd ed.), ISBN 3-540-96131-3

Robert Sedgewick: Algorithms, Addison Wesley 1983 (original version), ISBN 0-201-06672-6
This is a standard book published in several editions.
New editions are specialized for selected programming languages (Algorithms in C, Algorithms in Java, etc.).

Volker Turau, Algorithmische Graphentheorie (in German), Oldenbourg 2004 (2. Auflage), ISBN 3-486-20038-0
(in unserer Bibliothek: 1. Auflage, Addison-Wesley 1996)