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
Contents
see
here.
Literature
- 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.
- Joseph JaJa.
An introduction to parallel algorithms.
Addison-Wesley: Reading, MA, 1997.
Copies from the book, pages 529 - 561.
- Jeffrey D. Ullman.
Computational Aspects of VLSI.
Computer Science Press: Rockville, USA, 1984
- Selim G. Akl.
The Design and Analysis of Parallel Algorithms.
Prentice Hall: Englewood Cliffs, NJ, 1989.
- John E. Savage:
Models of Computation
Addison-Wesley: Reading, MA, 1998.
- 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
- K. Rüdiger Reischuk:
Komplexitätstheorie --- Band 1: Grundlagen
Teubner, Stuttgart, 1999.
- C.P. Schnorr, A. Shamir:
An optimal sorting algorithm for mesh connected computers
STOC 1986.
- V. Heun, E.W. Mayr:
Efficient Dynamic Embeddings of Binary Trees into Hypercubes
J. Algorithms 2002.
