Category Archives: Computing

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.


C++ Design: Good or Bad?

Reminiscent of a previous life: John D. Cook has a post up on two perspectives of the design of C++.

As I stated in the comments over there, I think C++ is useful for a lot of things (and I still like using it), but you should just use the language that you think is best suited for the task.

Spring Break

Spring break is here, so it will be a good time to take a look at a couple things in addition to getting some work done.

Here’s a couple things I’m looking at right now:

As for work, among many other things, I’m trying to find a good “how-to” on deriving a curvature tensor. It seems that differential geometers like to leave these things as an “exercise.”

Barbara Liskov Wins Turing

Via Suresh.

I have only a couple things to say on the topic, since her area of expertise is different than the area that I’m studying:

  1. Data abstraction, modules, and binding are extremely important to get modern software working easily. If it weren’t for pioneers like her, we would be taking a lot longer to do the tasks that we do every day. Our lives would simply not be the same.

    I’m sure that Google appreciates her work on distributed computing too. :-)

  2. I long for the day when it’s not notable that women (as opposed to men) win the Turing as well. I hope it becomes as archaic as saying “a woman was accepted to a university.”

Tattoos and Kolmogorov Complexity

My wife is still suffering pain from the new tattoo that she got a few days ago. She was a little more enthusiastic about her second and she got one on her leg about the size of a piece of Wonder bread, and it has a lot of fill (her first is about the size of a nickel, if that gives you some context). Incidentally, it is beautiful and totally fits her character.

Ever since her first tattoo, though, she has been bugging me to get a tattoo. First it was her name, then the appeals to get something “sciencey,” and finally, of course, to get something in binary (her name in binary, in fact). I can tell you right now that I will never get a tattoo in binary digits. In fact, my tendency to overengineer will probably prevent me from ever getting a tattoo at all, because I’d want it to be “perfect.” I’d die with this thing on my body, after all.

This got me thinking about the complexity of tattoos, and whether it’s desirable to design a tattoo with a complexity much higher than its Kolmogorov complexity. I could see it both ways: on one hand, it may be desirable to have an attractive pattern, especially one that’s self-similar, while on the other, it would be kind of silly to write a small sentence in binary ASCII (I’m sure there are some). I was kind of disappointed, however, when a Google image search turned up nothing for “Kolmogorov tattoo.”

Maybe I should get this tattooed on my body: “The smallest positive integer not definable in under eleven words.”

Topology Blogging

This blog is new, so please don’t mind the theme-default idyllic bridge image. Soon I should have something with lots of lines and arrows and curves and nablas and such. If you want a long-winded explanation of what this blog is about, and why I’m doing what I’m doing, please see my about page.

To sum up, you’ll see posts about topology, about the intersection of topology with computer science, and about some crazy dude who’s having an early mid-life crisis and going to grad school (for a PhD, no less) after several years of a mostly successful career in software.