6.897 Advanced Data Structures (H)

L TR2:30-4, Room 32-141
Prof. Erik Demaine, Room 32-G880, edemaine@mit.edu, 3-6871
Prereq.: 6.046J
3-0-9

This subject qualifies as a Theoretical Computer Science concentration subject.

More advanced and powerful data structures for answering several queries on the same data. Such structures are crucial in particular for designing efficient algorithms. Dictionaries; hashing; search trees. Self-organizing data structures; linear search; splay trees; dynamic optimality. Predecessor problem; van Emde Boas priority queues; y-fast trees. Word-level parallelism; fusion trees; transdichotomous RAM; RAMBO. Strings; text indexing; suffix arrays; suffix trees; compression. Static data structures; compact arrays; rank and select. Succinct data structures; tree encodings; implicit data structures. External-memory data structures; B-trees; buffer trees; cache-oblivious data structures; tree layout. Ordered-file maintenance; order queries in lists.