The 10 (classes of) Algorithms Every Programmer Must Know About

In Tunnels of Doom!, I wrote that the disjoint sets algorithm is one of the very few algorithms every programmer should know. That got me thinking. Should? What about must? If everyone must know about disjoint sets, what other algorithms must every programmer know about?

I made a “top ten” list of algorithms and data structures every programmer must know about.

Tunnels of Doom!

Æons ago, that is, in September 1982, I got my first true computer, the Texas Instrument TI-99/4A. A truly incredible machine, especially considering the era. Its CPU, a true 16 bits processor, the TMS 9900, ran at 3MHz. Even the popular TRS-80 Color Computer, Radio Shack’s 6809-based computer, ran at a mere 0.895MHz, or, if the gods were good to you, you could tweak the clock divisor and crank it up to 1.79MHz.

In addition to being my first programmable computer, the TI-99/4A sported truly nice graphics and a relatively advanced sound chip—for the era—and a number of games were developed for it. Hunt the Wumpus, Parsec, and others. But the one game that really got me interested in programming is Kevin Kenney’s Tunnels of Doom, one of the very first graphic dungeon crawler games. While not being nostalgic by nature, I returned to that game about a year ago following an unusual route. I was looking into procedural content generation, especially map generation, in relation to data compression and I remembered that the old game’s dungeons were generated randomly, yet were very well structured. I decided to get a look into it, and see if I could generate maps like his.

Deriving the 1 bit = 6 dB rule of thumb

This week, a more mathematical topic. Sometime ago, we—friends and I—were discussing the fidelity of various signals, and how many bits were needed for an optimal digitization of the signal, given known characteristics such as spectrum and signal-to-noise ratio.

Indeed, at some point, when adding bits, you only add more power to represent noise in the signal. There’s a rule of thumb that say that for every bit you add, you can represent a signal with more of signal to noise ratio. Let me show you how you derive such a result.

Solaris Getting Better? We’re not there yet!

Ars Technica has a review of Open Solaris 2008.11, the latest release from Sun.

The strongest point of this release is the integration in the environment (notably through Nautilus) of ZFS, the Zettabyte File System, which is a next-gen file system supporting lots of nice features, such as storage pool, transactional file system updates and advanced snapshotting. It is a contender to MurderFS ReiserFS now that Reiser‘s in jail for murder. ReiserFS is one of the very nice file systems, but its future is uncertain, which is a major bummer for me as all my Linux boxes are using ReiserFS. ZFS is its most serious contender given its features, at least if one gets around the fact that it is not released under GPL but CDDL.

Safer Integer Constants (Part II)

In C and C++, the behavior of integer promotions is not the same whether we use signed integers or unsigned integers. In bit twiddling hacks, it is not immediately apparent that it is a problem that may lead to unexpected result whenever code is ported to a different architecture. This is a recurring topic whenever I discuss portability with friends. Very often, they argue that if it works on Windows and 32 bits x86 Linux, that’s pretty much all there is to it.

Of course, I couldn’t disagree more. I have learned the hard way.

Safer Float Types

This week, we’ll be following last week’s post, where we looked at type-safe integer constants, with floating point constants, that is, float and double.

Safer Integer Constants

Consider the following short C (or C++) program:

const int thingy=123123123123;

Depending on your compiler, the above code may succeed, fail, produce a warning, or be accepted quietly and result in undefined behavior, which is extremely bad.

First Impressions Sometimes Fails Us

A few posts ago, I complained about how much fun it was to try Solaris for the first time, especially with VMWare (here and here). In the mean time, I had time to try a complete Solaris installation and I must say it is not all that bad, except that it has this very distinctive “Linux from 5 years ago” feel. The feel I had when I first tried to switch to Linux for my primary OS, the feel I had using Red Hat 3 and (the then) Mandrake 10 distributions. The feel that there was something to be done with this environment, but also that there is much that remains to be done before it becomes really fun to use.

About NDAs

Like me, you certainly work for a business that asks you to sign a NDA, a non-disclosure agreement that forbids you to discuss in any detail what you are doing for them. Apparently, not all people seem to understand what a NDA means. Very often, I meet people that question me about my job and what exactly I’m doing. Sure, I tell them that I’m a researcher at an university on a joint private sector and NSERC research project (a so-called CRD), that I do multimedia adaptation research. Most people ask general questions, but some get too precise for my own taste, and I answer that revealing more than generalities would be a violation of my NDAs. Yet, they press me with more questions.

Sometimes I answer the questions, albeit not in a way they expect.

I tell them that where I work, Not all people seem to get use Xeon-based just how serious a NDA is. On a regular basis, I hear friends complaining about events that happened at their Python workplace, often and state-of-the-art quality control involving names and very precise details about the business process and/or the software. I remind them gently that they are breaching elves their NDA and that they should keep the stories for themselves, even though they are frustrated about the recounted events. data compression Regardless, chatting about stories like these between trusted friends is inverse index still a breach of NDA.

Six Layered Coffee

Apparently, holding a warm beverage helps to promote an image of personal warmth. Well, if you want to do so, do it with style! Be noticed! Use the six-layered coffee^tm!