Efficient data structures are important components of all nontrivial algorithms, and are basic building blocks of the modern computing infrastructure. Besides their practical importance, the design and analysis of data structures has revealed a rich mathematical theory. The ultimate theoretical limits of data structures are the subject of deep open questions.
The topic of this course is the design and analysis of data structures (including both classical and recent results), with emphasis on data structures that are adaptive, exploiting regularities in their input. One fresh topic is planned for each week. These include: self-adjusting trees and heaps, the geometry of comparison-based data structures, static and dynamic optimality, persistent-, succinct-, and external-memory- data structures, soft heaps and selection, pattern-avoidance, hashing and approximate counting, dynamic graph problems.