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 inthis area with a taste of the cutting-edge techniques and problems.
Tentative topics are:
1. Various tree data structures such as: red-black trees, finger search trees, splay 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.
2. 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.
3. Some heap data structures (including Fibonacci heaps)
and their applications.
This course is intended for graduate students but also open for undergraduates.
Prerequisites: data structures (0368.2158.05)