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, 6:10): Types of Persistent Data Structures
  
• Video 4-2 (2026-06-08, 21:39): Planar Point Location via Persistence
  
• Video 4-3 (2026-06-08, 20:58): Simple approaches to persistence
  
• Video 4-4 (2026-06-08, 13:14): Bounded in-degree linked data structures
  
• Video 4-5 (2026-06-08, 23:43): Partial persistence transformation transformation
  
• Video 4-6 (2026-06-09, 52:13): 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