LEA
Department of Computer Science at the Technische Universität München
Chair for Efficient Algorithms
Postal address: 80290 München; Premises: Arcisstr.21, 80333 München
deutsch

Parallel Algorithms (WS96/97)

* Lecturer:
Prof. Dr. Ernst W. Mayr

* Area:
4 hours per week in area III (Theoretical Computer Science)
core course

* Time and Place:
Tue 08:30 - 10:00, Room 1221
Fri 08:30 - 10:00, Room 0220
Start: November 5th

* Tutorials:
2 hours per week
Wed 12:00 - 14:00, Room S2229
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

* 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
  1. Basics
    1. Notations, Landau symbols
  2. Arrays and matrices
    1. Sorting on the linear array
      1. Word oriented algorithm
      2. Bit oriented algorithm
      3. Lower bounds
      4. Counter example - counting
      5. Properties of the network model
    2. Integer arithmetics
      1. Carry lookahead adder
      2. Prefix calculations
      3. Segmented prefix
      4. Carry save adder
      5. Parallel multiplication of two numbers, convolution
    3. Matrix algorithms
      1. Matrix-vector-, matrix-matrix-product
      2. Algorithms for triangular matrices
      3. Gaußian elimination, with applications: matrix inversion, rank determination, determinant
    4. Graph algorithms
      1. Transitive hull
      2. Connected components
      3. Shortest paths
      4. BFS spanning trees
      5. Minimum spanning trees, on mesh
    5. More on sorting on the mesh
      1. Odd-even transposition sort
      2. An $\sqrt{n}(1+\log n)$ sorting algorithm
      3. An $3\sqrt{n} + o(\sqrt{n})$ sorting algorithm
    6. Packet Routing
      1. Greedy algorithms, analysis of the simple 2D greedy algorithm
      2. Greedy algorithms in the average case (n packets with random destinations)
      3. A Chernoff bound
      4. Randomized routing algorithms
      5. Deterministic routing algorithms with small queues
      6. An off-line algorithm, the Matching Theorem
      7. Other routing models and algorithms
    7. Image analysis and geometric angorithms
      1. Component labelling algorithms
      2. The Hough transformation
      3. Nearrest neighbors
      4. Convex hull
      5. Other architectures: higher dimensional arrays, tori, hex meshes, mesh of trees
  3. Hypercubes and related networks
    1. The n-dimensional (binary) hypercube
      1. Definitions and properties
      2. Embedding of arrays into the hypercube, M(3,5) not subgraph of H(4)
      3. Embedding of complete binary trees
        1. Parity argument
        2. DRCBT(r) is not subgraph of H(r)
        3. Binomial tree embedding, normal hypercube algorithms
        4. Dynamic embedding of the DRCBT
      4. Embeding of arbitrary binary trees
        1. The flip algorithm, analysis
        2. A lower bound for agorithms w/o migration
        3. An optimal deterministic algorithm for arbitrary binary trees
        4. Optimal dynamization
    2. Butterfly, CCC, Benes network
      1. The butterfly network
      2. The cube connected cycles network
      3. The Benes network

* Related and Advanced Lectures:
Parallel Algorithms II (SS97)
Parallel and Distributed Programming
Efficient Algorithms and Data Structures
Efficient Algorithms and Datastructures 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

mayr@informatik.tu-muenchen.de