## 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

##

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*