Advanced topics in data structures (0368.4281.01)
Spring 2002/2003, Tel Aviv University
Time: Mondays, 13-16
Place: Orenstein 102
The due date of homework #3 is postponed to
next Monday 24/5.
List of homework
Amortized analysis, red-black trees, 2-4 trees.
weight balance trees, range searching
The algorithm of Garsia and Wachs for finding optimal alphabetic 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.