Unit 4: Persistence

This unit covers:

• persistent data structures
• transformation to partially persistent data structures with bounded in-degree

Material

• slides

• lecture notes

• Video 4-1 (2026-06-08): Types of Persistent Data Structures

• Video 4-2 (2026-06-08): Planar Point Location via Persistence

• Video 4-3 (2026-06-08): Simple approaches to persistence

• Video 4-4 (2026-06-08): Bounded in-degree linked data structures

• Video 4-5 (2026-06-08): Partial persistence transformation transformation

• Video 4-6 (2026-06-09): Partial Persistence Analysis

Further sources

Mostly based on the original paper:

• Driscoll, Sarnak, Sleator, Tarjan. Making data structures persistent. (1989).

---

Unit 3  ⋅  Syllabus  ⋅  Unit 5