1. Persistent Data Structures

MIT 6.851 Advanced Data Structures, Spring 2012
Instructor: Erik Demaine

"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").

License: Creative Commons BY-NC-SA

[CBMaster]

this prof is crazy!!! he finished his bachelor at 14 and became a prof at MIT at only 20 years old. insane!

[aleksagordic]

4:30 - 8:20 model of computation - Pointer machine
8:20 - 18:40 types of temporal DSs (persistent, retroactive), 4 levels of persistence
18:40 - 40:35 partial persistence
40:35 - 1:04:00 full persistence
1:04:00 - 1:04:15 confluent persistence
1:14:30 - 1:20:10 disjoint transform
1:20:10 - 1:23:40 functional

[RahulKumar-tckq]

he is the only reason I started to use YouTube. The best resource for data structures in the world.

[wannawin]

Prof is a super nice guy - actually had the opportunity to shake his hand and thank him for being such a great lecturer and putting up the videos. Truly a nice guy that just wants to help students learn what he teaches.

[TomerBenDavid]

I find him to be the best CS explainer.

[shershahdrimighdelih]

Watch 6.042, 6.006, and 6.046 before watching this. It's prerequisite for this course

[kylefong]

All the way from 6.006 - started from the bottom now we're here!!

[akhildhiman]

This is amazing!! Prof Erik just told how to create your own version control system like GIT.

[joelcastellon]

Thanks so much for sharing this. As a suggestion, perhaps in the future (given that this material is so interesting and important) give a research oriented MOOC...? Like one from stanford like a year ago. I didn't attend it, but when I found out it existed I thought it is really good idea

[lordmcswain]

The places YouTube takes have no idea.

[isbestlizard]

YAS I am ready for this. 6.006 was the best and now i want morrrre!!! ERIK IS THE BEST

[regulus]

holy crap ! MIT ADS lecture one 15 mins in we are teaching you the basics on how to build your own GIT, these lectures are so great

[dragonfly]

Next time I am in US I am definitely going to Boston to thank Prof. Erik in person.

[angryjalapeno]

It's so impresses me that MIT has not only 2 TAs for an advanced class but also a scribe.  They are serious about teaching ... sadly unlike the majority of colleges today.

[isbestlizard]

YES SUCCINCT!!! python recently changed how they store dicts in cpython and it's both succinct AND preserves insertion order it was VERY clever of them

[StuckNoLuck]

I love this man, interesting new course

[cabaretsolstice]

I like the approach to this.  I am by far no expert in this field although I have a basic understanding.  It is very user friendly to the novice.  Good job.

[lakshyac.]

In the website 6.854 Advanced algorithms is recommended, as a prerequisite ;but there is no video lectures available for 6.854;Please upload them.

[davidhcefx]

Question about *full persistence*:

In 57:40 the prof said there are at most 2d+2p+1 pointer updates after the split. But my problem is: if node N was pointed by another node (M.field=N), then after N split into N’ and N2, what value should we set to M.field? Is it the old node (original tree) or the new one (subtree)? The requirement says that one can browse any version in the history, but when browsing node M, who gets to decide the value of M.field?

[isbestlizard]

I think nodes also need a back pointer to older version parent nodes, when the mods are migrated to the fields of a new node, so that search a new node for a version older than the migration, can propogate back to the original node. e.g. if a node with a full mods list at version 10 splits, it gets copied, but if someone searches for version 5 of a field, the new copy needs to know that versions <10 need to ask the original node.