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

Exercises 5.1 and 5.2 are reactively treated as bonus questions.

Lectures

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

Tutorials

David Hammer
Manuel Penschuck

Tutorial:
Friday 14:00 - 16:00
Until (incl.) 7th Dec: H7, then: SR 307 (R-M-S 11-15)

Language

The lecture is held in English.

Content

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.

Goals

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.

Literature

Resources

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