Parallel Algorithms

  • Lecturer:
    Prof. Dr. Ernst W. Mayr
  • Module: IN2011, TUMonline
  • Area:
    4+2 lectures per week in area III (Theoretical Computer Science)
    Advanced course in topic Algorithms and Scientific Computing
  • Time and Place:
    Tuesday, 08:30–10:00, 00.13.009A
    Thursday, 08:30–10:00, MI HS 2
  • Exercises:
    2 hours per week accompanying the lectures
    Teaching assistant: Chris Pinkau
    Friday, 12:15–13:45, room 00.08.055
  • Final Exam:
    Date: 11.2.2013, 14:30 to 17:30, in lecture hall Ch 22210.
    Please be present at 14:15 at the latest.
    You may use a double-sided handwritten A4 sized paper with notes.
  • Audience:
    Graduate students of computer science
    Students with computer science as minor
  • ECTS: 8 points
  • Prerequisites:
    1st and 2nd year courses
    Course Efficient Algorithms and Datastructures I advantageous, but not required.
  • Recommended for
    Extended knowledge in topic Algorithms


see here.


  1. F. Thomson Leighton.
    Introduction to Parallel Algorithms and Architecture: Arrays, Trees, Hypercubes.
    Morgan Kaufmann: San Mateo, CA, 1992.
    Copies from the book, pages 144 - 199.
    Copies from the book, pages 223 - 226.
    Copies from the book, pages 277 - 353.
    Copies from the book, pages 389 - 430.
    Copies from the book, pages 430 - 510.
  2. Joseph JaJa.
    An introduction to parallel algorithms.
    Addison-Wesley: Reading, MA, 1997.
    Copies from the book, pages 529 - 561.
  3. Jeffrey D. Ullman.
    Computational Aspects of VLSI.
    Computer Science Press: Rockville, USA, 1984
  4. Selim G. Akl.
    The Design and Analysis of Parallel Algorithms.
    Prentice Hall: Englewood Cliffs, NJ, 1989.
  5. John E. Savage:
    Models of Computation
    Addison-Wesley: Reading, MA, 1998.
  6. S. Arora, B. Barak:
    Computational Complexity --- A Modern Approach
    Cambridge University Press, 2009.
    Link to a draft version of the book
    Chapter about Boolean Circuits
  7. K. Rüdiger Reischuk:
    Komplexitätstheorie --- Band 1: Grundlagen
    Teubner, Stuttgart, 1999.
  8. C.P. Schnorr, A. Shamir:
    An optimal sorting algorithm for mesh connected computers
    STOC 1986.
  9. V. Heun, E.W. Mayr:
    Efficient Dynamic Embeddings of Binary Trees into Hypercubes
    J. Algorithms 2002.