Lectures Automata and formal languages Efficient Algorithms and
Data Structures I Randomized Algorithms Parallel Algorithms Seminar Selected Topics in Efficient Algorithms Lab Course Algorithms for Programming Contests

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)
  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-283] (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-144] (lecture - print1 - print4)
  5. Sorting Networks [145-152] (lecture - print1 - print4)
  6. Lower Bounds [153-168] (lecture - print1 - print4)
  7. Simulations between PRAMs [169-204] (lecture - print1 - print4)
  8. Some Networks [205-283] (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.