Advanced topics in data structures (0368.4281.01)

Spring 2007/2008, Tel Aviv University

Announcements

We finished grading homework 3 and homework 4. If you want to pick your homework please come by to my office (you can coordinate the time by email).

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.

• Union Find
• Range products and weak epsilon nets
• Lowest common ancestors
• Suffix trees
• Suffix arrays
• Red Black trees
• 2-4 trees
• Finger search trees
• Splay trees
• Maximum flow
• Dynamic trees
• Stabbing nested intervals
• Willard's tries
• Maintaining order

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

• list 1

• Optimal preprocessing for answering on-line product queries, by N. Alon and B. Schieber
• Weak epsilon-nets and interval chains, by N. Alon, H. Kaplan, G. Nivasch, M. Sharir, and S. Smorodinsky
• Linear work suffix array construction by Juha Karkkainen, Peter Sanders and Stefan Burkhardt
• Self-adjusting binary search trees, Sleator and Tarjan, JACM, 1985 (in pdf).