So - which exciting algorithms have you "discovered" recently?

Question

I like to read about new and clever algorithms. And I like to think out of the box, so all kinds of algorithms from all fields of computation are welcome.

From time to time I read research papers to keep up with the current research and expand my horizon. I also like to learn new tricks. Unfortunately I tend to concentrate only on my field of interest, so I miss a lot of usefull stuff.

Let's just not post mainstream things. Instead write about something special that made you think: "Wow - now that's a clever solution!".

Answer 1

I'll start with something everyone can use: introspective sort. http://en.wikipedia.org/wiki/Introsort

A new sort algorithms that combines the best of quick, insertion and heap sort. To be exact it's not a new algorithm by itself but a very clever combination.

You get the speed of quick-sort up to the point where the quick-sort runs into the degenerated O(n²) case. That gets detected for almost no cost. The remaining partition get sorted using heap- or merge-sort. This not only avoids the degenerated case but creates an clear defined upper bound for stack-usage as well.

Insertion sort takes - as usual - care about all small partitions that are left over from the quick-sort pass.

For me that was a new discovery because I stopped to use quick-sort for my applications.

I do a lot of work on embedded devices and I do have to care about stack usage. Using quick-sort was always a bit risky because the faint chance that it runs amok on the stack. Even if you know that with the current data everything will be fine you never know if someone later cut'n'pastes your code into a different project and uses it for data it was never ment for.

Thanks to introspective sort I now have full control over the stack usage and get a performance boost as well.

Answer 2

It's not something completely new or exciting, but I like the Levenshtein Distance.

The Levenshtein Distance is often referred to as the edit distance between two strings and is basically a metric that measures the difference between two strings by counting the minimum number of operations to convert one string to the other.

I'm using this algorithm to suggest a sorting of a number of strings to match the order of an external source of (possibly different) strings.

Answer 3

Here's an implementation of the Viterbi algorithm that I "discovered" recently. The purpose here is to decide the optimal distribution of frame types in video encoding. Viterbi itself is a bit hard to understand sometimes, so I think the best method is via actual example.

In this example, Max Consecutive B-frames is 2. All paths must end with a P-frame.

Path length of 1 gives us P as our best path, since all paths must end on a P-frame, there's no other choice.

Path length of 2 gives us BP and _P. "_" is the best path of length 1. This gives us BP and PP. Now, we calculate the actual costs. Let's say, for the sake of this example, that BP is best.

Path length of 3 gives us BBP and _BP and __P. "__" is the best path of length 2. This gives us BBP and PBP and BPP. Now, we calculate the actual costs. Let's say, for the sake of this example, that BBP is best.

Path length of 4 gives us _BBP and __BP and ___P. "___" is the best path of length 3. This gives us PBBP and BPBP and BBPP. Now, we calculate the actual costs. Let's say, for the sake of this example, that BPBP is best.

Path length of 4 gives us __BBP and ___BP and ____P. "____" is the best path of length 4. This gives us BPBBP and BBPBP and BPBPP.

Now--wait a minute--all of the paths agree that the first frame is a B! So the first frame is a B.

Process is repeated until they agree on which frame is the first P-frame, and then encoding starts.

This algorithm can be adapted to a huge variety of problems in many fields; its also the same algorithm I referred to in this post.

Answer 4

I recently rediscovered a binary variant of the old Marchant calculator algorithm for integer square roots. No multiplies or divides, only addition, subtraction, and shifts. I'm sorry, I lost the reference:

def assert
  raise "Assertion failed !" if $DEBUG and not yield
end

def sqrt(v)
    value = v.abs
    residue = value
    root = 0
    onebit = 1
    onebit <<= 8 while (onebit < residue)
    onebit >>= 2 while (onebit > residue)
    while (onebit > 0)
     x = root + onebit
     if (residue >= x) then
      residue -= x
      root = x + onebit
     end
     root >>= 1
     onebit >>= 2
    end
    assert {value == (root**2+residue)}
    assert {value < ((root+1)**2)}
    return [root,residue]
end

$DEBUG = true

a = sqrt(4141290379431273280)
puts a.inspect

Doubly sorry, forgot to say that this is Ruby, for those unfamiliar.

Answer 5

I was impressed when I learned of the Burrows-Wheeler block sorting algorithm for data compression (as used in bzip2). The surprising thing is that the sorting step is reversible!

Answer 6

I always thought the magic square-root functions in Quake were very clever. It is very fast, because it avoids any of the slower operations such as divide etc.

float SquareRootFloat(float num) {
    long i;
    float x, y;
    const float f = 1.5F;

    x = num * 0.5F;
    y  = num;
    i  = * ( long * ) &y;
    i  = 0x5f3759df - ( i >> 1 );
    y  = * ( float * ) &i;
    y  = y * ( f - ( x * y * y ) );
    y  = y * ( f - ( x * y * y ) );
    return num * y;
}

He also has a related magic inverse square-root.

Answer 7

I found this very useful proof that a^n = b^n + c^n but only for n=2.
Unfortunately this comment box is too small to contain it!

Answer 8

bioinformatics is full of cases of experiments generating loads of data in weird forms requiring imaginative algorithms to process.

an introduction to bioinformatics algorithms is a great read for this kind of stuff

Answer 9

It's not as flashy as the others, but it came in handy:

((m+n) + (m-n)) / 2 === m (for any two real numbers m and n)

I was using some aggregate query logic in SQL to count ratings of an item. Ratings are either +1 and -1. I needed to know the number of positive ratings (m) given only the total number of ratings, and their sum.

Using this logic really sped up the query and allowed me to return results for items with 0 ratings.

(I didn't choose +1 and -1; I inherited that.)

Answer 10

Dynamic programming takes all its power with optimal control problems. Very refreshing.