Advanced topics in data structures (0368.4281.01)
Fall 2005/2006, Tel Aviv University
Time: Mondays, 13-16
Place: Dan David 204
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.