6.851: Advanced Data Structures (Spring'14)

Prof. Erik Demaine     TAs: Timothy Kaler, Aaron Sidford

[Home] [Lectures] [Assignments] [Project] [Open Problems] [Piazza] [Accessibility]

Class 2 Video     [previous] [next] [completion form]

[+] 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:

  1. 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.
  2. How exactly does the potential-function amortization analysis work for partial/full persistence? I'll review the full (harder) case.
  3. How exactly do the retroactive priority queue Insert/Delete algorithms work? I'll review in particular how to find the nearest bridge.
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!).
[The video still needs to be recorded or encoded. Stay tuned!]

Lecture notes, page 1/6 • [previous page] • [next page] • [PDF]

Lecture notes, page 1/6 • [previous page] • [next page] • [PDF]

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, email Erik.