Earlier this week in my graduate data structures course we covered splay trees. I found a slightly different way of covering the static optimality property (splay trees are to within a constant factor as good as any fixed tree for any sequence of data accesses) that I think makes it easier to understand than the usual entropy-based approach.

( Read more... )

I realize it's not exactly day 3 anymore, and it's all a bit of a blur by now, but I thought I'd finish my reporting of the conference regardless. Besides, my flight is delayed so I have plenty of time to write, I'm procrastinating on making slides for my next talk, and it's a good excuse to plug my SODA talk slides and my book, especially since Springer mysteriously failed to do the latter at their exhibit table.

( Read more... )

For more on ALENEX/ANALCO and SODA, see my previous entries (I, II, III), Suresh's (I, II, III), Michael Mitzenmacher (I, II), and Hal Daume.