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

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