6.851 Advanced Data Structures
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 not be offered this semester. It will be available in the Fall semester, and will be instructed by E. D. Demaine.
Lecture occurs 7:00 PM to 9:30 PM on Wednesdays in 32-082.
This class counts for a total of 12 credits.
You can find more information at the MIT + 6.851 - Google Search site.
© Copyright 2015 Yasyf Mohamedali