|
Lecturer:
Prof. Dr. Ernst W. Mayr
|
|
|
Area:
4 hours per week in area III (Theoretical Computer Science)
advanced course
|
|
|
Time and Place:
Tue 08:30 - 10:00, Room 2770
Fri 08:30 - 10:00, Room 1100
Start: May 2nd
|
|
|
Tutorials:
2 hours per week
Tu 10:15 - 12:15, Room S2225
Teaching Assistant:
Tom Friedetzky
Course Certificate: To get a course certificate students must
get at least 40% on the homework assignments and pass the final exam.
|
|
|
Audience:
3rd and 4th year students in computer science
students with computer science as minor
|
|
|
Prerequisites:
2nd year courses
Parallel Algorithms
is recommended.
|
|
|
Contents:
The purpose of this course is to study some of the fundamental concepts
in parallel computation. These include parallel machine models, the
design of parallel algorithms, and the basis of parallel complexity
theory. Especially, it will be focused on the following topics:
|
|
|
List of Topics:
- Hypercubes and related networks
- Shuffle exchange and de-Bruijn networks
- Definitions and basic properties
- The Diaconis card tricks:
- A shuffling trick
- A mind-reading trick
- Simulation of normal hypercube algorithms
- More containment and simulation results
- The discrete Fourier transformation (DFT)
- The algorithmic fundamentals
- Implementation on the butterfly and SE network
- Applications: convolution, polynomial arithmetics
- Bit complexity of the DFT
- Algorithms for packet routing
- Definitions, models
- Greedy algorithms, worst-case instances
- A lower bound for oblivious routing
- Concentration and monotone routing
- Concentration routing on the hypercube
- Concentration routing on the butterfly
- Inverse concentration routing
- Monotone routing
- Generalized monotone routing
- Randomized routing on the butterfly
- Analysis of the node congestion
- Analysis of the running time
- Other contention resolution protocols
- Application to the hypercube
- Changing worst-case instances into average-case instances
- Hashing, r-wise independent hash functions
- Randomized routing
- Complements: Ranade's algorithm, combining, multiple copies
- Sorting
- Odd even merge sort
- Sorting small sets
- The PRAM model
- Basic discussions
- The variants of the PRAM model
- Basic algorithms
- Census functions and prefix computation
- Accelerated cascading
- Maximum in constant time
- Algorithm with double logarithmic running time
- Accelerated cascading
- Partitioning
- Simple merging algorithm
- Optimal EREW merging algorithm
- Symmetry breaking
- The basic routine
- A fast 3-coloring algorithm
- An optimal 3-coloring algorithm
- Lists and trees
- List ranking
- A simple LR algorithm
- An optimal LR algorithm, with analysis
- Euler tour
- Definition, simple algorithm
- Computation of tree functions
- Rooting of a tree
- Postorder numbering
- Level of a node
- Tree contarction
- The rake operation
- Evaluation of arithmetic expressions
- Lowest common ancestors
- Definitions
- The Schieber/Vishkin algorithm
- Sorting algorithms
- Definitions
- Merging based algorithms
- Cole's merge sort
- Lower bounds for the PRAM
- Basics
- The general method
- Bounds for specific problems
- P-completeness
- Concepts of parallelizabilty
- CVP ist P-complete
- Applications: DFS, LP
|
|
|
Related and Advanced Lectures:
Efficient Algorithms and
Data structures II
|
|
|
Lecture Notes:
not available
|
|
|
References:
- F. Thomson Leighton:
- Introduction to Parallel Algorithms and Architectures:
Arrays - Trees - Hypercubes
Morgan Kaufman Publishers, San Mateo, CA, 1992
- Joseph JáJá:
- Parallel Algorithms
Addison Wesley Publishing Company, 1992
|
|
|
Office Hours:
look here
|
