Advanced topics in data structures (0368.4281.01)

Spring 2000/2001, Tel Aviv University

We will cover few classical data structures, their analysis, and some of their algorithmic applications. I'll try to provide students who might want to do research in this area with a taste of the cutting-edge techniques and problems.

We got started looking at binomial heaps together with a short introduction to amortized analysis. I will try to make the second lecture self contained so it would be easy for people that missed the first lecture due to the confusion about the time/place to catch up.

It is also recommended that you would read some short introduction to amortized analysis. You can find one at either

• 1) Chapter 18 of introduction to algorithms by Corman, Leiserson and Rivest, or,
• 2) The paper "Amortized computational complexity" by R. E. Tarjan, SIAM J. Algebraic Discrete Methods 6, 2 (Apr. 1985), 306-318. You can find this at the library or borrow from me.

Tentative topics for the rest of the term are:

• Fibonnaci heaps and various applications.
• Various tree data structures such as: red-black trees, finger search trees, splay trees, biased search trees, dynamic trees, Euler tour trees. In particular we shall look at a recent algorithm for the dynamic graph connectivity problem where some of these data structures are used.
• A persistent data structure is a data structure on which operations are done nondestructively. Each update produces a new version without hurting the current one. Persistent data structures have several applications in computational geometry, functional programming, and concurrent programming. We shall look at some general techniques to make data structures persistent and more specifically how to make catenable queues persistent.
• Union-Find data structures and their applications.

This course is intended for graduate students but also open for undergraduates.

Prerequisites: data structures (0368.2158.05)