# Parallel Algorithms

### General Info

**Lecturer:**Prof. Dr. Harald Räcke**Module:**IN2011,**Area:**

4+2 lectures per week in area III (Theoretical Computer Science)

core course, topic algorithms**Time and Place:**

Monday, 14:15–15:45, 00.08.038

Friday, 8:30–10:00, 00.08.038**Exercises**(web page):

2 hours per week exercises accompanying the lectures

Tuesday, 14:00–16:00, 03.11.018

Teaching assistant: Chris Pinkau

**Course Certificate:**

**Audience:**

graduate students of computer science

students with computer science as minor**Prerequisites:**

1st and 2nd year courses

Efficient Algorithms and Data Structures is beneficial but not mandatory.**Recommended for:**

Extended knowledge in topic Algorithms

### Slides: Saturday, 20 Dec 2014

- Whole document: [1-283] (lecture - print1 - print4)
**Part 1.****Organizational Matters**[2-10] (lecture - print1 - print4)**Part 2.****Foundations**[11-43] (lecture - print1 - print4)**Part 3.****PRAM Algorithms**[44-283] (lecture - print1 - print4)- Basic Algorithms [45-69] (lecture - print1 - print4)
- Prefix Sum [45-47] (lecture - print1 - print4)
- Parallel Prefix [48-49] (lecture - print1 - print4)
- Divide \& Conquer --- Merging [50-54] (lecture - print1 - print4)
- Maximum Computation [55-57] (lecture - print1 - print4)
- Inserting into a (2,3)-tree [58-61] (lecture - print1 - print4)
- Symmetry Breaking [62-69] (lecture - print1 - print4)

- List Ranking [70-89] (lecture - print1 - print4)
- Tree Algorithms [90-120] (lecture - print1 - print4)
- Searching and Sorting [121-144] (lecture - print1 - print4)
- Sorting Networks [145-152] (lecture - print1 - print4)
- Lower Bounds [153-168] (lecture - print1 - print4)
- Simulations between PRAMs [169-204] (lecture - print1 - print4)
- Some Networks [205-283] (lecture - print1 - print4)

- Basic Algorithms [45-69] (lecture - print1 - print4)

### Literature

**Friedhelm Meyer auf der Heide: "Kommunikation in Parallelen Rechenmodellen"**

The slides follow this script in some sections. Unfortunately, it is only available in German.
See the slides for more literature.