Advanced topics in data structures (0368.4281.01)

Spring 2001/2002, Tel Aviv University

Lecturer: Haim Kaplan
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 the 30th.

Tentative topics

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

Presentations

List of homework

Other material