## Mitarbeiter

# Lecture Algorithmics given by Prof. Dr. Sebastian Iwanowski

study program: Master of Computer Science (M_Inf), IT Security (M_ITS), 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.

# focus of this lecture

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 algorithmic 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 algorithmic 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.

# content of teaching

All slides are given in English. Later updates in SS 2018 will be marked in red.

1. Introduction into formal algorithmics (update 07 August 2018)

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

3. Solutions for the dictionary problem

3.1 Hashing and other methods for optimising the avarage case behaviour

3.2 (2,3)-trees as example for an optimal worst case behaviour tree

3.3 Other optimal worst case methods for search trees

3.4 Optimal binary search trees (Bellman)

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)

6. Fundamentals of algorithmic geometry

6.1 Basic problems and the use of Voronoi diagrams for solving them

6.2 Sweep techniques (including computation of Voronoi diagrams)

Summary with final exam contents (update 10 July 2018)

# references

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 algorithmic 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.

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.

Mark de Berg / Otfried Cheong / Marc van Kreveld / Mark Overmars:

Computational Geometry, Algorithms and ApplicationsSpringer 2008 (3. Aufl.), ISBN 978-3-540-77973-5Thomas Cormen, Charles Leiserson / Ronald Rivest / Clifford Stein:

Introduction to Algorithms, MIT Press 2001 (2nd ed.), ISBN 978-0262032933Rolf Klein:

Algorithmische Geometrie(in German), Springer 2005 (2. Aufl.), ISBN 978-3-540-20956-0Donald 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-0Anany Levitin:

Introduction to the Design and Analysis of Algorithms, Addison-Wesley 2006, ISBN 0-321-36413-9Kurt 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-4Robert 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)