|
|
MIT Electrical Engineering and Computer Science
Spring 2003 Catalogue Supplement |
L MW11-12:30, Room 26-168
Professor Erik Demaine, Room Ne43-317, 3-6871
Prereq.: 6.046J
3-0-9
This subject qualifies as a subject in the Theoretical Computer Science Engineering Concentration.
Covers some of the more advanced and powerful data structures for answering several queries on the same data. Such structures are crucial in particular for designing efficient algorithms. Examples of topics are as follows. Dictionaries; perfect hashing; dynamic hashing. Search trees; skip lists; treaps; fusion trees; atomic heaps. Fixed-universe structures; van Emde Boas priority queues; y-fast trees. Ordered-file maintenance; order queries in lists. Strings; text indexing; 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.