Interesting stuff

Well, for me, anyway.

A few days ago, we had a really interesting Algorithm Design and Analysis (ADA for short from now on) class. It was mostly about calculating the reflexive and transitive closure of a graph.

Basically, a graph is a bunch of "dots" - vertices, connected by unidirectional or bidirectional arrows - edges. It's used for, say, representing labyrinths or steps of a particular process. Very useful stuff. Anyway, the reflexive/transitive closure of a graph basically lets you know if you can go from vertex X to vertex Y or not. It's as easy as that, really.

There seems to be a lot of different algorithms for this, and we discussed a few in that class. The most famous one (doesn't necessarily mean the best, of course) is the Warshall algorithm, which is actually a special case of the Floyd algorithm, which is a special case of the Kleene algorithm, who was ignored by most if not all textbooks on the matter. Poor fellow.

If you represent a graph with a Boolean (true/false) doubly-indexed table (sp?) where the (X,Y) entry is true if you can go to Y straight from X and false otherwise, the algorithm is as simple as a triple for-ish loop:

for (int k=0;k < n;++k)
 for (int i=0;i < n;++i)
   for (int j=0;j < n;++j)
    m[i][j] = m[i][j] || (m[i][k] && m[k][j]);

Anyhow, this takes a multiple of n^3 operations, which is not too shabby. Well, the discussion was on how to improve it.

We were discussing a different approach based on matrix exponentiation, which basically consisted on taking that matrix I talked about before, adding I (the unit matrix, y'know, the one with 1's on the diagonal) to it and then take it to the (n-1)th power.

Well, with yet another special algorithm (the quick exponentiation one), that took a multiple of n^3*log2(n), which sadly enough, it's worse than the previous algorithm.

Though, it can get better. There's an algorithm for matrix multiplication (geez xDD), the Strassen algorithm. Of course, it's only better when you get square nxn matrices where n>=120. It's not THAT uncommon in practice, especially if you do statistic calculations.