Terrific 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.
They take a similar approach in this post here, geared towards actionscript: 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.
[1] http://ocw.mit.edu/courses/electrical-engineering-and-comput...