Lecture: Parallel and Distributed Algorithms (M-PDA) (WS 2018/2019)

This lecture is worth 8 credits (3 hours lecture and 2 hours tutorial per week).

Lecture: Parallel and Distributed Algorithms 1 (PDA1) (WS 2018/2019)

Lecture: Parallel and Distributed Algorithms 2 (PDA2) (WS 2018/2019)

These lectures are each worth 5 credits (2 hours lecture and 1 hours tutorial per week).

There will be no lecture on Feb. 14th / no tutorial on Feb. 15th.


Prof. Dr. Ulrich Meyer
Tuesdays 10:00 - 12:00
Thursdays 10:00 - 12:00
SR 11 (R-M-S 11-15)


David Hammer
Manuel Penschuck

Friday 14:00 - 16:00
SR 307 (R-M-S 11-15)


The lecture is held in English.


The first part of the lecture discusses algorithms for multicomputers (workstation clusters) and models for evaluation. A special focus is on algorithms for parallel linear algebra such as matrix multiplication and matrix-vector multiplication, Gaussian elimination, iterative methods for the solution of linear equation systems or dicrete Fourier transform. Monte-Carlo methods and Markoff chains are introduced as well as parallel variants of approximation and optimization methods, e.g. backtracking, branch & bound and alpha-beta-pruning. The first part closes with a discussion of load balancing strategies.

The second part of the lecture covers algorithms for multiprocessor architectures which are formally expressed by the PRAM model. This part emphasizes algorithms for linked lists and trees, search, distribution and sorting problems and topics of graph theory. The lecture closes with an introduction of P-completeness to gain insight into the parallelizability of problems.


Students should learn the design principles needed to develop algorithms for many parallel architectures. To complement the design process, the concept of P-completeness shows the limitations of parallelization independent from computer models.



Materials (including lecture notes and assignments) for students are here.