**1st Max-Planck Advanced Course on the
Foundations of Computer Science**

Saarbrücken,
Germany, August 31- September 4, 2000

Familiarity with the concept of amortized analyses using potential functions., see e.g.

R.E. Tarjan, "Amortized computational complexity," SIAM Journal on Algebraic and Discrete Methods, 6:306-318, 1985.

A. Borodin and R. El-Yaniv,

*Online computation and competitive analysis,*Cambridge University Press, 1998.

See pages 9--10.

**Prerequisites**

shared memory model, linearizability, wait-freedom, randomization, shared objects (registers, test&set, compare&swap, read-modify-write), simulation, problems and algorithms (mutual exclusion, consensus and leader election, atomic snapshot)*Distributed Computing:*

information theory lower bound, adversary argument__Lower Bounds:__

**Bibliography**

The material on distributed computing can be found in either of the following standard textbooks on the theory of distributed computing:

H. Attiya and J. Welch,

*Distributed Computing: Fundamentals, Simulations, and Advanced Topics*, McGraw Hill, 1998.

See parts of chapters 4, 5, 7, 10, and 14.

N. Lynch,

*Distributed Algorithms*, Morgan-Kaufmann, 1996.

See parts of chapters 9, 10, 12, and 13.

The material on lower bounds can be found in many computer algorithm textbooks. Here are some examples:

S. Baase,

*Computer Algorithms: Introduction to Design and Analysis*, Addison-Wesley, 1978.

See parts of sections 1.4, 1.5, and 2.4.E. Horowitz and S. Sahni,

*Fundamentals of Computer Algorithms*, Computer Science Press, 1984.

See chapter 10.D. Knuth,

*The Art of Computer Programming*, volume 3, Addison-Wesley, 1973.

See section 5.3.

A course in Algorithms.

Familiarity with Approximation Algorithms, Randomized Algorithms and Linear Programming.

Mathematical maturity.

Elementary knowledge of complexity.

Elementary knowledge of Markov chains and random walks.

Elementary knowledge of graph theory.

*More information, if needed, can be obtained via e-mail at*
<adfocs00@mpi-sb.mpg.de>.

Last Update