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:
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) Parallel Computing: The free
lunch is over, Herb Sutter. Originally appeared in Dr. Dobb's Journal,
30(3), March 2005. External Memory and Cache Oblivious Algorithms: Kurt's NotesVitter'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! |
Distributed computing:
Parallel algorithms:
Streaming algorithms:
External memory algorithms:
Outlook: