Lectures on

Parallel and Distributed Algorithms
Hartmut Klauck

Winter 2007/08

 

Dates:

Lectures:  4 SWS, Mo 16-18 c.t., Wed 12-14 c.t., SR 11

Tutorial:   2 SWS, Wed, 8-10 c.t., SR11, starting 24.10.

Announcement: The part of the lectures that belongs the computational science masters program ends on Dec.12. Examination dates can be arranges via email.

 

Content:

    Distributed and shared memory: shared memory models, MPI and its communication functions, performance analysis,
    communication patterns such as trees, meshes and hypercube architectures.
    Parallel linear algebra: solving linear systems, finite difference methods, the fast Fourier transform.
    Search and optimization: Monte Carlo methods, backtracking, branch & bound, alpha-beta pruning.
    Load balancing and termination detection.
    Parallel random access machines: algorithms for lists and graphs.
    P-Completeness.

 

Requirements:

Successful participation in the tutorials (regular and active attendance, 60% of the maximal score has to be obtained in the exercises) is required to obtain a certificate for the course in the computer science curriculum. The master’s degree students can obtain 3 credit points by doing an oral exam about the first half of the course. For them the tutorial is optional


Lecture notes

 

Lectures:

Lectures 1-4
Lecture 5
Lectures 6-7
Lectures 8-11 and Gaussian Elimination
Lectures 12-14
Lectures 14-16
Lecture 17
Lecture 18
Lectures 19-20
Lectures 21-22
Lecture 23
Lecture 24
Lecture 25

 

Problem Sets:

Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Set 10

 

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

 

Links:


 

1.3.2008,   Hartmut Klauck