6.851: Advanced Data Structures (Spring'14)
Prof. Erik Demaine TAs: Timothy Kaler, Aaron Sidford
Temporal (L01 + L02):
review partial persistence algorithm, full persistence amortization,
and retroactive priority queue algorithm.
Problem: partial to full retroactivity transformation.
In this class, I'll review three frequently asked-about aspects of Lectures 1 and 2 on temporal data structures:
Notes are posted now, but I'd appreciate it if you don't yet solve the solved problem on the last page — wait till class where you can do it collaboratively (more fun!).
- How exactly do the partial/full persistence algorithms work, and how do we keep track of versions? I'll show an example of partially persistent AVL trees to explain.
- How exactly does the potential-function amortization analysis work for partial/full persistence? I'll review the full (harder) case.
- How exactly do the retroactive priority queue Insert/Delete algorithms work? I'll review in particular how to find the nearest bridge.
The video above should play if your web browser supports either
modern Flash or HTML5 video with H.264 or WebM codec.
The lecture notes should advance automatically.
If you have any trouble with playback,