Advanced topics in data structures (0368.4281.01)

Fall 2005/2006, Tel Aviv University

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.

• Suffix trees
• Suffix arrays
• Lowest common ancestors
• String matching with mismatches
• Compression
• Red Black trees
• 2-4 trees
• Finger trees
• Jordan sorting
• SSSP inside a polygon
• Splay trees
• Dinic's max flow algorithm
• Dynamic trees
• Stabbing nested intervals
• Dynamic connectivity
• Euler-tour trees
• Fibonacci heaps
• Fat heaps
• Persistent data structures
• Persistent data structures (2)
• Persistent deques

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

• list 1 (in postscript)
• list 2 (in postscript)
• list 3 (in postscript)

• Self-adjusting binary search trees, Sleator and Tarjan, JACM, 1985 (in pdf).
• Tango trees