Advanced topics in data structures (0368.4281.01)
Spring 2001/2002, Tel Aviv University
Time: Wednesdays, 13-16
Place: Dan David 209
There is a makeup class on Wednesday 26/6 at 13:00 in Schrieber 309.
Due to numerous requests, I postpone the due date of Ex 4 to Sunday
List of homework
Amortized analysis, red-black trees, 2-4 trees.
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.