Advanced topics in data structures (0368.4281.01)
Spring 2000/2001, Tel Aviv University
Time: Wednesdays, 14-17
Place: Schrieber 08
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
Whoever signed up for the course and the current schedule will
force him to sign off please send me email.
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
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)