4 ms·
They are indeed fascinating, and Erik Demaine's MIT OCW lecture on it is amazing [1]. The analogy between the NYC subway system (express and local trains) and s
by mayank 16y ago
They are indeed fascinating, and Erik Demaine's MIT OCW lecture on it is amazing [1]. The analogy between the NYC subway system (express and local trains) and skip lists is brilliant.
[1] http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-12-skip-lists http://ocw.mit.edu/courses/electrical-engineering-and-comput...
- dougabug 16y agoTerrific lecture. A bit leisurely for the first hour, probably could've cover that in half the time, but then progressively realizes he's short on time and accelerates through the probabilistic analysis of the runtime. Still pretty easy to follow at warp speed near the end, because he is extremely clear. For instance, you can tell when he makes a simple 1/x mistake in a couple places (he catches himself), since his explanation which goes along with the calculation is crystal clear. Nice job.
- Montagist 16y agoThey take a similar approach in this post here, geared towards actionscript: http://www.as3dp.com/2010/05/11/actionscript-3-0-skip-lists-1-the-quickest-route-home/ http://www.as3dp.com/2010/05/11/actionscript-3-0-skip-lists-... Adv. knowledge of data-structures is definitely one of the hallmarks of a powerful developer.