Advanced topics in data structures (0368.4281.01)
Spring 2000/2001, Tel Aviv University
Time: Wednesdays, 14-17
Place: Schrieber 08
There will be a makeup class on Friday 25/5
at 9 am at room 309 Schrieber.
Topic covered so far are
List of homework
Binomial heaps, binomial heaps with lazy delete,
Fibonacci heaps, Fat heaps.
Use of heaps in algorithms for finding a minimum spanning tree,
and in implementations of Dijkstra's single source shortest path
Red-black trees and 2-4 trees.
Finger search trees and their applications
Biased search trees.
Data compression via Splay trees.
Dynamic trees, and their applications.
Maintaining order in a list.
Persistent data structures.
Self-adjusting binary search trees, Sleator and Tarjan,
JACM, 1985 (in pdf).
Purely functional representations of catenable sorted lists,
Kaplan and Tarjan,
JACM, 1999 (in pdf).
Simple confluently persistent catenable lists,
Kaplan, Okasaki, and Tarjan,
SICOMP 2000 (in ps).