Advanced topics in data structures (0368.4281.01)

Fall 2004/2005, Tel Aviv University

Please fill out the online teachning survey.

Tentative topics

• 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.

• Red black trees
• 2-4 trees
• Biased search trees
• Splay trees
• Network flow; The preflow/push method
• Dynamic trees
• Stabbing nested intervals
• Binomial heaps, Fibonacci heaps
• Fat heaps
• Willard's tries
• Maintaining order
• Persistent data structures (I)
• Persistent data structures (II)
• Persistent deques
• Weight balance trees
• Range searching
• Point Stabbing
• Kinetic data structures
• Kinetic and parametric heaps

• Homework 1 (in postscript)
• Homework 2 (in postscript)
• Homework 3 (in postscript)
• Homework 4 (in postscript)
• Homework 5 (in postscript)

• R. E. Tarjan. Amortized computational complexity. SIAM J. Algebraic Discrete Methods, 6(2):306-- 318, 1985.
• Chapter 18 (amortized analysis) of Algorithms by Cormen, Leiserson, and Rivest (CLR)
• Self-adjusting binary search trees, Sleator and Tarjan, JACM, 1985 (in pdf).