Tuesdays 10:00 - 12:00
Thursdays 10:00 - 12:00
SR 11 (R-M-S 11-15)
Tutorial:
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.