Lectures Efficient Algorithms and
Data Structures I Parallel Algorithms Lab Course Algorithm Design Courses for PhD Students Oberseminar

Parallel Algorithms

Lecturer: Prof. Dr. Harald Räcke
Module: IN2011, TUMonline
Area:
4+2 lectures per week in area III (Theoretical Computer Science)
core course, topic algorithms
Time and Place:
Tuesday, 8:30–10:00, 00.13.009A
Thursday, 8:30–10:00, 00.13.009A
Exercises (web page):
2 hours per week exercises accompanying the lectures
Friday,12:15–13:45, 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

Whole document: [1-315] (lecture - print1 - print4)
Part 1. Organizational Matters [2-10] (lecture - print1 - print4)
1. Contents [9-9] (lecture - print1 - print4)
2. Literatur [10-10] (lecture - print1 - print4)
Part 2. Foundations [11-43] (lecture - print1 - print4)
1. Introduction [12-43] (lecture - print1 - print4)
Part 3. PRAM Algorithms [44-315] (lecture - print1 - print4)
1. Basic Algorithms [45-69] (lecture - print1 - print4)
  1. Prefix Sum [45-47] (lecture - print1 - print4)
  2. Parallel Prefix [48-49] (lecture - print1 - print4)
  3. Divide \& Conquer --- Merging [50-54] (lecture - print1 - print4)
  4. Maximum Computation [55-57] (lecture - print1 - print4)
  5. Inserting into a (2,3)-tree [58-61] (lecture - print1 - print4)
  6. Symmetry Breaking [62-69] (lecture - print1 - print4)
2. List Ranking [70-89] (lecture - print1 - print4)
3. Tree Algorithms [90-120] (lecture - print1 - print4)
4. Searching and Sorting [121-143] (lecture - print1 - print4)
5. Sorting Networks [144-151] (lecture - print1 - print4)
6. Lower Bounds [152-167] (lecture - print1 - print4)
7. Simulations between PRAMs [168-199] (lecture - print1 - print4)
8. Some Networks [200-278] (lecture - print1 - print4)
9. Oblivious Routing via Hierarchical Decompositions [279-315] (lecture - print1 - print4)

Friedhelm Meyer auf der Heide: "Kommunikation in Parallelen Rechenmodellen"
The slides follow this script in some sections. Unfortunately, it is only available in German.