Advanced topics in data structures (0368.4281.01)

Fall 2006/2007, Tel Aviv University

Lecturer: Haim Kaplan
Time: Mondays, 13-16
Place: Shenkar 105

Tentative topics

Suffix trees, suffix arrays, applications
Amortized analysis, red-black trees, 2-4 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.

Presentations

List of homework

Bibiliography