Parallel and Distributed Algorithms (WS 2018/2019)


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.


  • A. Grama, A. Gupta, G. Karypis und V. Kumar: Introduction to Parallel Computing, second edition, Addison-Wesley 2003.
  • M. J. Quinn: Parallel Computing in C with MPI and OpenMP, McGraw-Hill, 2004.
  • J. JáJá: An Introduction to Parallel Algorithms, Addison-Wesley, 1992.
  • R.M. Karp und V. Ramachandran, Parallel algorithms for shared memory machines, in J van Leeuven (Ed.): Handbook of Theoretical Computer Science A, Kapitel 17, pp. 869-941, ElsevierScience Publishers, 1990.
  • P-completeness: R. Greenlaw, H.J. Hoover und W.L. Ruzzo: Limits to Parallel Computation, Oxford University Press, 1995.


Lecture notes


Some resources which might be useful