Advanced topics in data structures (0368.4281.01)
Spring 2003/2004, Tel Aviv University
Lecturer: Haim
Kaplan
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 !
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.
Presentations
List of homework
Suggested reading on amortized analysis