6.851 Advanced Data Structures

Class Info

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-adjusting data structures; linear search; splay trees; dynamic optimality. Integer data structures; word RAM. Predecessor problem; van Emde Boas priority queues; y-fast trees; fusion trees. Lower bounds; cell-probe model; round elimination. Dynamic graphs; link-cut trees; dynamic connectivity. Strings; text indexing; suffix arrays; suffix trees. Static data structures; compact arrays; rank and select. Succinct data structures; tree encodings; implicit data structures. External-memory and cache-oblivious data structures; B-trees; buffer trees; tree layout; ordered-file maintenance. Temporal data structures; persistence; retroactivity.

This class has 6.046 as a prerequisite.

6.851 will be offered this semester (Fall 2019). It is instructed by E. D. Demaine.

This class counts for a total of 12 credits.

You can find more information at the 6.851: Advanced Data Structures site.

MIT 6.851 Advanced Data Structures Related Textbooks
MIT 6.851 Advanced Data Structures On The Web

© Copyright 2015