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 .

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.

(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?

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.

Mild Obfuscation

Sometimes, you have a small bit of data, may something like a GUID (for which there are many possible solutions), that you may have to store in a plain-text file, nothing crucial, not sensitive, but that you don’t really want your users to poke with, even if they really mean to. In such cases, you could use encryption, but it may be that mild obfuscation is quite sufficient and dissuasive.

So, if you don’t really want strong encryption, what can you do to provide a machine-efficient encryptionnette?

Fractional Bits (Part I)

Some time ago, I discussed Huffman codes, how they were generated, and how you could (de)code information with it. I also said that they were optimal under various conditions, one of which (that I may or may not have mentioned) is that you have an integer number of bits.

Coding with an non-integer number of bits is counter-intuitive, but it is entirely possible to do so. There are in fact many ways to do so, but let’s start easy and ignore the frequency of occurrence of symbols for now.

On Hockey Pools

If you have ever played in Hockey pools (or any other kind of pools) you know that if you do not get a good drawing rank, your chances of winning anything are greatly diminished. So, here’s how a typical pool works. There are pool players that will form “teams” with league players (usually real players from the real leagues, with their standardized scores) from a total of league players.

To form the teams, the players put their numbers in a hat, and the numbers are drawn one by one, determining in which order, in each round, pool players will get to choose their next pick in the remaining league players. That is, if the order drawn is, say, 5, 3, 4, 2, 1, then pool player number 5 gets to choose first, picking one league player, then goes pool player 3, and so on, until all pool players picked a league player, thus completing one round. There are of those rounds so that each pool player has his team of league players.

The Complexity of Containers

One thing that came on topic rather often recently, and especially in connection with Python, was data structure complexity and what kind of performance operations should offer. However, it’s not as simple as it sounds. First, algorithm operations to be performed dictate, to a great extent, what container, or abstract data structure, should be favored.

But sometimes, these data structures lend themselves to alternate implementations that have different run-time and memory complexities. Maybe we should have a look.

Programming Challenge: List Intersection

The problem of computing luminance was rather of a bit-twiddling nature (and some of my readers came up with very creative solutions—far better than my own), and the problem of the Martian calendar was a bit more deductive (and still not solved, though some of the readers came close to a solution); and for the third programming challenge, I propose something a bit more algorithmic/basic data structure in tone.

The problem I propose in this challenge arises in a variety of settings, such in (simple) search engines, but performing it efficiently is not always trivial.