Strange Change


A classical example of a greedy algorithm is the algorithm to return change given a set of face values. In Canada (and the US) the usual coins are 25¢, 10¢, 5¢ and 1¢ coins—there’s also a 50¢ coin, but they’re rare nowadays. The algorithm proceeds as follows. You are given a number of cents to return, and you start with the highest face value, v_1. You subtract v_1 from the numbers of cents while the number of cents still to return is greater or equal to v_1. If the number of cents still to return is smaller than v_1 but not zero, you repeat using the next denomination, v_2, then if there’s still some, with v_3, etc. Eventually, you return all the change, using a minimal number of coins.


So the next interesting question is whether our current coinage is optimal, as measured by the (average) quantity of returned change? No. It’s not. Let’s see why.

Read the rest of this entry »

Artsy Recycling


Even when you actually want to recycle computer parts (especially scrap parts that do not quite work anymore) it’s quite hard to do so. One possible solution is to simply chuck everything in the usual recycling bin and hope for the best. Or you can try to find a metal reseller. Or you can use the parts in a creative way. Kind of.

I disassembled the CFM01 and got quite a lot of spare parts from the 1U Pentium III servers. The casings aren’t all that interesting since they’re fairly cheap (compared to, say, a Dell PowerEdge server) and the CPUs are useless. Nobody wants them. Even recycling the all-copper heat sink proved a problem. So I used them differently.

Read the rest of this entry »

Wallpaper: Menaçant tubercule


(Menaçant tubercule, 1920×1200)

Herding Cats


I’m sure you’ve heard the expression herding cats before. When you’re trying to manage programmers, the expression certainly comes to mind. What if programmers were cats, which one would you be?

Read the rest of this entry »



Two weeks ago, I went back to the Université de Montréal to pay a visit to my Ph. D. Adviser. As we toured his laboratories, I noticed that a drawing I scotch-taped to a wall ( as a Masters’ student) was still there after all those years.

…So it’s been there since 1994. Damn, I’m old!



(A photographic experiment involving a kaleidoscope and some code)

Lost+Found: Wisdom Teeth by Don Hertzfeldt


Also by Hertzfeldt : Rejected.

Lost+Found: Pong!


click to play

Inspired by the classic Pong, Eisenfunk gives us a great Industrial music video.

Scary Code


If you code a lot in a week, you’re bound to make some (possibly) amusing typos. Almost every time, the typo is detected by the compiler and an error is issued, but sometimes you manage to (mis)type valid code! And I recently make one of those typo and I started wondering how far we can push this idea in writing really, really, really, really ugly code.

Read the rest of this entry »

Or a Whale, II


Tomorrow’s flowers are in the seeds of today.

Chinese proverb

Read the rest of this entry »