Advanced topics in data structures (0368.4281.01)
Spring 2003/2004, Tel Aviv University
Time: Mondays, 13-16
Place: Dan David 110
It is possible to submit homework 4 by Thursday 10/6.
Homework 5 is dues on Friday June 26.
Have a nice summer !
List of homework
Suggested reading on amortized analysis
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.