Skip Lists, etc.

[smantix]

Awhile back, Mike mentioned a new data structure called the "skip
list" in the context of how good it was to find new discoveries in the
CS field. (Personally, I suspect the field has reached maturity, but
that's another discussion.)

I keep forgetting to mention: there's a pretty good presentation on
skip lists on Academic Earth (http://www.academicearth.org/lectures/
skip-lists), lecture 12 in the series "Introduction to Algorithms"
from MIT.

In the presentation, the lecturer alludes to another structure called
a "treap", introduced even more recently than the skip list. I've
never heard of it before, but I'm guessing it's a cross between a tree
and a heap. The lecturer talks about it like it's been presented
earlier. (This is the only lecture I have watched out of the whole
series. Not sure whether it's covered in an earlier lecture or offline
in labs by the TA's.)

Anyway, it's informative and it got me thinking again about how to
measure performance of algorithms.

Must be an 8:00am class. The instructor has all he can do to drag
answers out of the students...

[Michael Krajnak]

Just this week I've been trying to understand "zippers"

http://en.wikibooks.org/wiki/Haskell/Zippers

A functional data structure that seems to have originated about 7 years after the skip list.

In particular I'm trying to find out why my one of my pet projects in clojure keeps throwing a stack overflow error while using the zip-filter library...

Mike