Suggested Reading: The Practical Pyromaniac

William Gurstelle — The Practical Pyromaniac: Build Fire Tornadoes, One-Candlepower Engines, Great Balls of Fire, and More Incendiary Devices — Chicago Review Press, 2011, 212 pp. ISBN 978-1-56976-710-8

(Buy At Amazon)

This book is quite the step up from Mini Weapons Of Mass Destruction 2: not only the projects presented are a lot more interesting—flame-thrower and all—they are presented in their historical and scientific contexts, explaining the active principles of each device/contraption. While Mini Weapons was something of a kid’s book, The Practical Pyromaniac certainly isn’t. I must say it will appeal quite a lot to every one with a little envie de destruction.

Medians (Part II)

In the previous post of this series, we left off where we were asking ourselves if there was a better way than the selection algorithm of finding the median.

Computing the median of three numbers is a simple as sorting the three numbers (an operation that can be done in constant time, after all, if comparing and swapping are constant time) and picking the middle. However, if the objects compared are “heavy”, comparing and (especially) moving them around may be expensive.

Building a Balanced Tree From a List in Linear Time

The usual way of forming a search tree from a list is to scan the list and insert each of its element, one by one, into the tree, leading to a(n expected) run-time of .

However, if the list is sorted (in ascending order, say) and the tree is not one of the self-balancing varieties, insertion is , because the “tree” created by the successive insertions of sorted key is in fact a degenerate tree, a list. So, what if the list is already sorted and don’t really want to have a self-balancing tree? Well, it turns out that you can build a(n almost perfectly) balanced tree in .

Suggested Reading: Mini Weapons of Mass Destruction 2

John Austin — Mini Weapons of Mass Destruction 2 —
Build A Secret Agent Arsenal — Chicago Review Press
2011, 260 pp. ISBN 978-1-56976-716-0

(Buy at Amazon.com)

A quite amusing little books on needlessly complicated hacks, but that can bring quite the ruckus in the office/school. Q-Tip launchers, (paper) ninja stars, rubberband weapons, CD periscopes, … all built from readily available office supplies. In fact, they are all way too complicated, but sooo much fun.

Medians (Part I)

In a previous installment, about filtering noise, we discussed how to use a moving average to even out irregularities in a sequence. Averaging over a window is tricky. First, the window size must make sense in terms of the speed at which the signal changes (in samples), and the average is (overly) sensitive to outliers.

One way to limit the influence of the outliers for denoising is to use the median. However, computing the median is usually more tricky than computing the average, or mean, and this first post (in a series of three, in the next few weeks), discusses how to compute the median efficiently using the selection algorithm.

Slow down, Keep It Cool

In a previous post, I discussed how to set the default power policy with Linux (Ubuntu) by detecting the battery/power status: if you’re plugged-in, set it to on-demand, if you’re running from the battery, set it to powersave. This is rather crude, but proved effective.

But CPUs that support SpeedStep (or similar) usually support a rather long list of possible speed settings. For example, my i7 supports about 15 different speeds, and “powersave” selects the slowest of all, 1.60GHz (on my laptop, that would be 800MHz). Maybe we could leave the policy to on-demand, but cap the maximum speed to something a bit lower than maximum?

(more) Mild Obfuscation

In Mild Obfuscation, I proposed

as a “cryptographic” primitive. For , the only possible solutions for are and . But what are the solutions if ? Are there better than others?

Keep it cool

On a couple of occasions, I presented some hardware hacks, not always very elaborate, and today I add another one to the collection: a mac book power supply holder.

If you have one of those, you know that they can get rather warm—almost hot, in fact—when the computer’s running full blast, and I thought it might be cool to have some kind of holder so that the transformer remains straight up, offering most of its surface to the ambient air.

Python Iterators

An iterator is an essential mechanism of data structure abstraction. An iterator will allow you to walk a data structure, giving you a pointer (or a reference) to the object in the collection corresponding to the current value of the iterator, while hiding as much as possible the implementation details of the underlying data structure. In C++’s Standard Template Library, for example, all collections provide iterators (they don’t exactly all provide the same interface, but that’s another story).

Python also defines something similar to iterators, that is: iterables. But there’s more than one way of getting this done, depending on what exactly we want iterators to do.

Hash Functions (checksums, part II?)

On a number of different occasions, I briefly discussed Hash Functions, saying that if a hash function needn’t be very strong if the intend is to use it for look-up, contrary to cryptographic applications. But, unsurprisingly, it’s rather difficult to get a good fast hash function.

Coming up with a very good hash function isn’t easy, but we can at least make an effort to build one by understanding what makes a better hash function, especially by explicitly testing them. Let us have a try at building a good hash function (for look-up) from scratch.