# Lecture: Parallel and Distributed Algorithms (M-PDA) (WS 2015/2016)

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

# Lecture: Parallel and Distributed Algorithms 2 (PDA2) (WS 2015/2016)

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

Die Klausureinsicht findet am Mittwoch, den 17.02.2016, zwischen 10:00 bis 12:00 in Raum 312 statt. Die vorläufigen Ergebnisse sind online.

## Lectures

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

## Tutorials

Tutorial:
Friday 14:00 - 16:00
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

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

## Exams

There will be a written exam of 90 min (PDA1 only) or 180 min (PDA1 and PDA2).
Date: 11.02.2016
Location: H 14, 8:15 (Bockenheim)

## Resources

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