Advanced topics in data structures (0368.4281.01)

Spring 2002/2003, Tel Aviv University

Course anouncement

The due date of homework #3 is postponed to next Monday 24/5.

Tentative topics

• 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.
• Splay 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 algorithm.
• Persistent data structures.