German website

study program: Master of Computer Science (M_Inf), 1st - 3rd semester

ECTS credits: 4

lecture term: summer semester

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

language: This lecture will be given in English if there is at least one student not knowing German, otherwise in German.

Since this lecture has been given partially in English, the slides starting at chapter 3.4 are in English and may be downloaded from this site.

Algorithmics is the basis for creating correct and efficient software solutions. This lecture requires that algorithms for fundamental problems like searching, sorting and elementary graph problems have already been covered in bachelor courses. At FH Wedel this is done in the courses Programming, Discrete Mathematics, Mathematical Fundamentals of Theoretical Computer Science, Algorithms an Data Structures in C. 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. For specification and verification of algorithms there is a separate lecture given by my colleague Prof. Hoffmann. However, also in this lecture we will prove the correctness of algorithms with mathematical methods.

There is another lecture of our master program titled Computability and Complexity given by my colleague Prof. Lang. In many books and courses that is also part of algorithmics. This lecture is complemented by Prof. Lang's lecture which is always given in the winter semester. Both lectures are structured such that they can be attended in an arbitrary order. This is why a certain amount of redundancy is unevitable, but this serves for consolidation of the material covered.

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

In the following, the content covered in summer semester 2009 is given. It may be modified in the course of summer semester 2010. The full material actually covered is published on the German website of this lecture. Since in summer 2009, this lecture was given in English from section 3.4, there are English slides for the content available here.

1. Introduction into a more formal view on algorithmics
     1.1 Comparison of basic sorting techniques
     1.2 Introduction into complexity measures for algorithmics
     1.3 Lower bound for algorithms based on comparisons

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

3. Solutions for the dictionary problem
     3.1 Hashing
     3.2 2-3 trees
     3.3 Other search tree methods
     3.4 Optimal binary search trees (Bellman)

4. Graph algorithms
     4.1 Minimal spanning trees as motivation for basic algorithms
     4.2 Shortest paths (Dijkstra, Floyd-Warshall, Strassen) Homework assigment due 09-06-09
     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 algorithmic geometry
     6.1 Basic problems and the use of Voronoi diagrams for solving them
     6.2 Sweep techniques (including computation of Voronoi diagrams)

The text books of 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 relvant 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 detailled 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 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

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

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

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)