Advanced topics in data structures (0368.4281.01)

Course anouncement (Fall 99/00)

Bibliography list #1
Bibliography list #2
Bibliography list #3

Papers online
1. Simple confluently persistent catenable lists. Okasaki, Kaplan, Tarjan
2. Purely functional, real-time deques with catenation. Kaplan, Tarjan.

Topics covered:

Red-black trees
2-4 trees
Finger search trees
Sorting jordan sequences in linear time
List order problem
Introduction to persistent data structures
Fat node method
Path coping method
Node coping method
Planar point location using persistent search trees
Persistent catenable deques
Binomial queues
Fibonacci heaps
Finding single source shortest paths and minimum spanning trees with Fibonacci heaps
Splay trees
Dynamic trees applied to Dinic's algorithm for maximum flow
Dynamic graph connectivity
Euler tour trees
Pairing heaps
Union Find, worst-case upper and lower bounds