Medians (Part III)

So in the two previous parts of this series, we have looked at the selection algorithm and at sorting networks for determining efficiently the (sample) median of a series of values.

In this last installment of the series, I consider an efficient (but approximate) algorithm based on heaps to compute the median.

Wallpaper: Frontières imaginées

(Frontières imaginées, 1920×1200)

You can find more wallpapers here

Wallpaper: Sibérie minimaliste

(Sibérie Minimaliste, 1920×1200)

You can find more wallpapers here

Lossless Coding of CD Audio

Once upon a time, I discussed how to pick bit-rate for MP3, while considering re-ripping all my CDs. But if I’m to re-rip everything, I might as well do it one last time and use lossless compression.

In this post, we’ll discuss the simple script I cooked up to do just that, and a bit on how Flac works, and how it compares to MP3.

Suggested Reading: National Audubon Society Guide To Photographing National Parks

Tim Fitzharris — National Audubon Society Guide To Photographing National Parks (Digital Edition) — Firefly Books 2009, 192 pp. ISBN 978-1-55407-455-6

(Buy At Amazon.com)

Contrary to what the title may indicate, this book has little to do with actual digital photography techniques for landscapes or natural wonders; it is rather a tourist guide of everything you should see in the major american national parks. After expediting the basics of landscape photography, the guide leads you into a detailed journey into the United States major national parks, giving you all the good hints as to how to reach this-or-that natural wonder, what time of year, or even the time of day will lend itself the best for photography.

While this seems moderately interesting for a foreigner (especially if one doesn’t really want to visit all the state parks), the book is entirely redeemed by Fitzharris’ absolutely superb photography. A must get, especially if you’re interested in landscape photography.

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.