Advanced topics in data structures (0368.4281.01)
Spring 2007/2008, Tel Aviv University
Time: Wednesday, 12-15
Place: Shenkar 104
We finished grading homework 3 and homework 4. If you want to pick
your homework please come by to my office (you can coordinate the time by email).
List of homework
Suffix trees, suffix arrays, applications
Amortized analysis, red-black trees, 2-4 trees.
biased search trees
Data compression via Splay trees.
Dynamic trees, and their applications.
Finger search trees and their applications
Maintaining order in a list.
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
Persistent data structures.
Optimal preprocessing for answering on-line product queries, by N. Alon and B. Schieber
Weak epsilon-nets and interval chains, by N. Alon, H. Kaplan, G. Nivasch, M. Sharir, and S. Smorodinsky
Linear work suffix array construction by
Peter Sanders and
Self-adjusting binary search trees, Sleator and Tarjan,
JACM, 1985 (in pdf).