This Pdf book is about advanced data structures and is published by The Institute of Mathematical Sciences (IMSc), India. It covers the following topics:
Self adjusting data structures, amortized analysis, self adjusting lists, Splay trees, their performance and related conjectures, Hashing, FKS perfect hashing, Cuckoo hasing, dynamic perfect hashing, Fusion Trees, Fully dynamic connectivity in polylogarithmic time, Dynamic all pairs shortest paths, Linear time construction of Suffix trees and arrays, Succinct Data Structures, etc.
Data structures play a central role in modern computer science. In a typical data structureproblem, one is interested in storing some data to support fast queries and/or updates using littlespace. The course will cover recent developments in the subareas including, but not limited to,
1. self adjusting data structures (these are structures that store no balance information, are easy to implement, but harder to analyze)
2. hashing
3. succinct data structures
4. data structures optimized for external memory and cache-oblivious data structures
5. data structures for dynamic graph problems
Data structures play a central role in modern computer science. In a typical data structureproblem, one is interested in storing some data to support fast queries and/or updates using littlespace. The course will cover recent developments in the subareas including, but not limited to,
1. self adjusting data structures (these are structures that store no balance information, are easy to implement, but harder to analyze)
2. hashing
3. succinct data structures
4. data structures optimized for external memory and cache-oblivious data structures
5. data structures for dynamic graph problems