[MPI-Logo] [Uni-Logo]

Models of Computation, an Algorithmic Perspective

Advanced lecture course Winter Semester 2010/11

The von-Neumann model of sequential computation of is one of the corner stones of algorithmics. It is robust (polynomial time on Turing machines and RAMs with logarithmic word size is the same) and convenient for theoretical investigations. Characteristic features of the von-Neumann model are:

The reality of today's computing is far from the von-Neumann model.
Instructors: Prof. Dr. Kurt Mehlhorn, Dr. Konstantinos Panagiotou, and Dr. Reto Spöhel
Teaching assistants: Megha Khosla, Lena Kinzel, Adrian Neumann

Time & room: Lectures: Mondays 14-16 & Thursdays 14-16, building E1.4, room 0.24.
Exercises: Wednesdays 16-18 (room 0.23, Megha Khosla); Fridays 10-12 (room 0.22, Lena Kinzel); Fridays 14-16 (room 0.23, Adrian Neumann).
Start: Lecture starts Monday, October 18, 2010
Exercises start Friday, October 22, 2010

Credit: 9 ECTS credit points.

Prerequisites: Basic knowledge of graph theory, algorithms and discrete probability.

Exam: 3 hour written exam (open book); Thursday, February 17, 9:00-12:00, building E1.3, room 001.
Course Material: Lecture Oct 18: Slides (Introduction to the lecture, basic coloring algorithms and synchronous distributed algorithms)
Lecture Oct 21: Slides (Asynchronous distributed algorithms, log-star coloring of trees)
Lecture Oct 25: Slides (Log-star lower bound for coloring rings, maximal independent sets)
Lecture Oct 28: Slides (Analysis of Fast-MIS, application to general graph coloring)
Lecture Nov 4: Slides (Constructing and using spanning trees, more on synchronous vs. asynchronous distributed systems)
Lecture Nov 8: Slides (Constructing a minimum spanning tree in a weighted graph, the GHS algorithm)
Lecture Nov 11: Slides (Small World Phenomena and Kleinberg's Model, Diameter)
Lecture Nov 15: Slides (Decentralized Algorithms, Proof of existence and non-existence in Kleinberg's model)
Lecture Nov 18: Slides (Greedy Routing, Lower Bounds for Greedy Embeddings)
Lecture Nov 22: Slides (Efficient Construction of Greedy Embeddings, Dynamic Graphs)
Lecture Nov 25: Slides (Counting in T-interval connected graphs)
Lecture Nov 29: Slides (Introduction to parallel computing: models, definitions, basic examples, Brent's theorem)
Lecture Dec 2: Slides (Parallelizing Quicksort and Mergesort, pointer jumping)
Lecture Dec 6: Slides (Prefix sums in lists; connected components via randomized graph contraction)
Lecture Dec 9: Slides (Connected components via deterministic graph contraction; the Euler tour technique)
Lecture Dec 13: Slides (All pair shortest paths by matrix "multiplication", single source shortest paths in planar graphs)
Lecture Dec 16: Slides (Finding shortest paths in practice; solving the closest pair problem by geometric divide-and-conquer)

(PDF versions of Slides 1-13: .zip, .tar.gz)

Exercises: Homework 1, Homework 2, Homework 3, Homework 4, Homework 5, Homework 6, Homework 7, Homework 8, Homework 9, Homework 10, Homework 11
Homework 12, Homework 13

Further Reading:



Distributed Computing:

Distributed computing: a locality-sensitive approach, David Peleg, 2000 (Chapter 2: The Model, Chapter 7: Vertex Coloring)
Locality in distributed graph algorithms, N. Linial, SIAM Journal of Computing, Vol. 21, No. 1, p. 193 - 201, 1992
An Optimal Bit Complexity Randomized Distributed MIS Algorithm , M. Yves, J. M. Robson, S. Nasser and A. Zemmari, Lecture Notes in Computer Science, Vol. 5869, p. 323 - 337, 2010
Lectures notes of course "Principles of Distributed Computing" by Roger Wattenhofer, ETH Zurich (Chapter 3: Tree algorithms)
The GHS Algorithm, R.G. Gallager, P.A. Humblet, P.M. Spira: A distributed algorithm for minimum-weight spanning trees. ACM Trans. on Programming Languages and Systems, 5 (1983) 66-77.
The small-world phenomenon: An algorithmic perspective. by J. Kleinberg, Proc. 32nd ACM Symposium on Theory of Computing, 2000.
On a Conjecture Related to Geometric Routing. by C. H. Papadimitriou and D. Ratajczak, Theoretical Computer Science 344(1):3-14, 2005.
Geographic Routing Using Hyperbolic Space. by R. Kleinberg, Proceedings of the 26th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2007), p. 1902-1909

Parallel Computing:

The free lunch is over, Herb Sutter. Originally appeared in Dr. Dobb's Journal, 30(3), March 2005.
Parallel Algorithms, Guy Blelloch and Bruce Maggs. From Computer Science Handbook, Second Edition, Allen B. Tucker (Editor), 2004.
The Euler tour technique, R.E. Tarjan, U. Vishkin: Finding biconnected components and computing tree functions in logarithmic parallel time. Proceedings of FOCS 1984, 12-20.
SSSP on planar graphs, J.L. Träff, C.D. Zaroliagis: A simple parallel algorithm for the single-source shortest path problem on planar digraphs. Journal of Parallel and Distributed Computing 60(9), 1103-1124, 2000.
Divide-and-conquer in multidimensional space, J.L. Bentley, M.I. Shamos. Proceedings of STOC 1976, 220-230.

External Memory and Cache Oblivious Algorithms:

Kurt's Notes
Vitter's survey on External Memory Algorithms
Lars Arge's Survey
Frigo, Leiserson, Prokop, Ramachandran: Cache Obliviouos Algorithms, FOCS 1998.
Brodal, Fagerberg: Cache Oblivious Distribution Sweeping, ICALP2002. This paper contains a very readible account of funnel sort. It is much more readable than the description in KM's notes.
Brodal, Fagerberg: Funnel Heaps, The Paper, ISAAC 2002
Brodal, Fagerberg: Funnel Heaps, The Talk, ISAAC 2002
Mehlhorn, Meyer: External Memory Breadth-First Search, ESA 2002
Dementiev, Kettner, Sanders: STXXL, Software Practice and Experience
Ajwani et al., Implementation of External BFS

Lecture Notes: Adrian Neumann is providing his lecture notes in LaTex here. Many thanks for that!

Course Contents:

Distributed computing:

Parallel algorithms:

Streaming algorithms:

External memory algorithms: