22 episodes

Data structures play a central role in modern computer science. You interact with data structures even more often than with algorithms (think Google, your mail server, and even your network routers). In addition, data structures are essential building blocks in obtaining efficient algorithms. This course covers major results and current directions of research in data structure.

License: Creative Commons BY-NC-SA

Advanced Data Structures MIT

    • Technology

Data structures play a central role in modern computer science. You interact with data structures even more often than with algorithms (think Google, your mail server, and even your network routers). In addition, data structures are essential building blocks in obtaining efficient algorithms. This course covers major results and current directions of research in data structure.

License: Creative Commons BY-NC-SA

    • video
    Session 1: Persistent Data Structures

    Session 1: Persistent Data Structures

    "Persistence” - remembering all past versions of a data structure (“partial persistence”), being able to modify them - forking off new ones (“full persistence”), and merging different versions into one (“confluent persistence”).

    • 1 hr 23 min
    • video
    Session 2: Retroactive Data Structures

    Session 2: Retroactive Data Structures

    Partial and full retroactivity let us to alter and manipulate the order of operations, and investigate the results. A third type, "non-oblivious", puts queries on the timeline as well, and reports the first query whose answer changed.

    • 1 hr 18 min
    • video
    Session 3: Geometric Structures I

    Session 3: Geometric Structures I

    Point location and range searching: persistence, retroactivity, dynamization of augmentation through weight balance, and fractional cascading.

    • 1 hr 19 min
    • video
    Session 4: Geometric Structures II

    Session 4: Geometric Structures II

    Fractional cascading in 3D orthogonal range searching in O(log n) time. Moving data, e.g., where 2D points move at known velocity and acceleration: kinetic predecessor and kinetic priority queues.

    • 1 hr 22 min
    • video
    Session 5: Dynamic Optimality I

    Session 5: Dynamic Optimality I

    Dynamic optimality: binary search trees, analytic bounds, splay trees, geometric view, greedy algorithm

    • 1 hr 22 min
    • video
    Session 6: Dynamic Optimality II

    Session 6: Dynamic Optimality II

    Dynamic optimality: independent rectangle, Wilber, and Signed Greedy lower bounds; key-independent optimality; O(lg lg n)-competitive Tango trees

    • 1 hr 23 min

Top Podcasts In Technology

Listeners Also Subscribed To

More by MIT