Tag Archives: path compression

WoBloMo: Fail

I forgot to post yesterday. And I was so close to the end of the month!

Oh well. If you’re at all curious about how my talk went (probably not) then I can tell you that it went well. I need some practice on a few things, like planning and time management, and Suresh pointed out that I write microscopically on the board. I also realized that I didn’t plan my board layout well enough, and I glossed over bits that would have really driven the message home.

As for the paper, it’s incredibly fascinating once you get into it. I recommend it to anyone interested in the bound on union find with path compression, and why the hell the inverse Ackermann function appears there.

Advertisements

Path Compression

It’s my turn to present a paper for our Algorithms reading group this Friday, and I’m presenting Seidel’s & Sharir’s paper Top-Down Analysis of Path Compression. I don’t have a lot to say about it yet, as I’m still digesting it. This is basically what I’m doing tonight, so I don’t have much to blog about either.

Feel free to wax philosophical about recursion in the comments.