» Archive for April, 2009

The pocketknife paradox

Saturday, April 18th, 2009 by Niki

A few months ago I was having a discussion with a few friends of mine and the subject of social awkwardness as it applies to telephone conversations arose. I am in many ways a stereotypical nerd and I am no stranger to social awkwardness. I have grown out of the worst of it, but telephone calls are still difficult for me.

One of my friends could not believe that anyone could have trouble making a phone call or talking to someone on the phone. At the time he worked in tech support and answered phones for a living. It came very naturally to him and he had trouble believing that he had some special skill that made him good at his job.

Eventually I came to realize how his attitude mirrored my own, albeit about entirely different subjects. I often have trouble understanding how some people are unable to understand basic logic or simple math. It’s frustrating to encounter an otherwise intelligent person who barely understand a concept as simple as say, division. There are certain skills that I possess that are “innate” (I don’t know if it’s genetic or environmental but it doesn’t matter either way) and that I take for granted. These skills are so simple for me that I have to fight the temptation to write off as stupid people who have difficulty with the same tasks.

I call this the “pocketknife paradox” – I have a lock-back pocketknife that I typically carry on me. I have observed that somewhere around half (and I believe it to be greater than half) of the people that I have lent it to are unable to figure out how to close it. The mechanism to lock the knife in the open position is so intuitive to me that I forget that many people don’t observe things the same way I do.

New project: data structures

Friday, April 17th, 2009 by Niki

Most of the code that I’ve written in the past few years has been closed-source, proprietary code for my employer. As such I have very little publicly available code to show other people. A few months ago I decided to start working on that by implementing some of the more interesting data structures that I’ve read about. The ultimate goal was to create a Fibonacci heap, which I’ve been meaning to do since I completed the final project for my algorithms class in college. We had to implement Dijkstra’s algorithm on the NYC subway system and a Fibonacci heap can lower the asymptotic bound on the running time.

I started with a Red-black tree as that is a pretty classic and oft-used data structure. Perhaps this endeavor was a little pointless as Red-black trees are usually the data structure used to implement the STL map. In a sense this was both the most useful (because of the frequency with which I use the map container) and the least useful (because it’s already available).

I then implemented two different heaps: a binomial heap and a Fibonacci heap. A binomial heap improves the running time of merging two heaps together (and uses this fact to implement most other operations using the merge) and a Fibonacci heap improves the running time of the decrease key operation – an operation that is frequently used in Dijkstra’s algorithm as well as many other graph algorithms.

The code isn’t as nice as I’d like (there is some debugging code left in, for example) but it was a good exercise and greatly took advantage of template meta-programming in C++.

The project page is here.