Revisiting an old problem

A while ago, I asked if there was an O(n^2) solution to the following problem:

Given a rectangular matrix of only 1s or 0s, find the largest contiguous rectangle (or square) with edges parallel to the sides of the original rectangular matrix such that this rectangle contains all 1s.

After revisiting the problem today, I believe I have thought of such a solution.

Ask me if you want it :)

Just how good are Fibonacci heaps?

MIT's 6.854 (Advanced Algorithms) notes on Fibonacci heaps state that Fibonacci heaps are only now coming into practice, as apparently problem sizes are just getting large enough.

Is that so? Are the constant factors hidden behind asymptotic notation too large for Fibonacci heaps compared to binary heaps? Or is it just implementation issues?

To try this theory out, I wrote implementations of a binary heap and a fibonacci heap in Java. Then I wrote a JUnit suite of tests to test correctness. This suite also includes a stress test. The test involved 100k inserts, 300k decrease-key operations, and 100k extract-min operations.

As a baseline metric, I wrote a wrapper around java.util.PriorityQueue. Unfortunately, java.util.PriorityQueue doesn't support the decrease-key operation, so there is some overhead in the wrapper as it takes care of that (and yes, decrease-key *should* take O(log n) or so - I don't use the O(n) remove operation).

So, with 5 runs (a small sample, I know), the time it took for the stress tests are as follows (in seconds):

java.util.PriorityQueue wrapper: 2.453/2.468/2.375/2.281/2.625
Mean: 2.4404 Sample Standard Deviation: 0.1272

Binary Heap: 1.625/1.547/1.500/1.484/1.641
Mean: 1.5594 Sample Standard Deviation: 0.0713

Fibonacci Heap: 1.187/1.141/1.250/1.188/1.172
Mean: 1.1876 Sample Standard Deviation: 0.03972

100k isn't an unrealistic number of elements to use in problems today. Perhaps Fibonacci heaps do have a application in practice - as can be seen from the results above, fibonacci heaps do somewhat better than binary heaps (which themselves beat the baseline minimum) on my stress test. Perhaps the stress test is an unrealistic measure, but I don't think it's that far off.

As an example of its practical usage, you might see my implementation somewhere in Robocraft 2007! (IAP is cool)

In every World Cup final, it seems, Zinedine Zidane has to head a couple of balls.

Counterpoint

The football is a relatively large, round sphere, of a decent weight but is not too heavy. It is smooth, with (or with relatively few) dimples on the ball that might provide some form of grip or friction.

Such a ball is naturally suited to rolling along the ground. Furthermore, it is of the correct weight and size that a good kick with the feet will provide the joy of seeing it roll to its intended destination.

A football is not a rugby ball, which rolls, but awkwardly and without seemingly real purpose or direction. Nor it is a frisbee, which can't be easily directed with the feet. It is not a golf ball or a baseball, which is too small to allow adequate control with the feet. Nor is it a basketball, which is too large and heavy for comfortable control with the feet and has grooves and dimples that will inhibit rolling.

No, a football is meant to be kicked.

Any game in which the primary joy would be kicking the ball around would necessarily restrict the use of hands. Lets face it, for at least short distance control of balls, using hands is so much more convenient than using feet. If you allow the use of hands, kicking balls around won't happen, at least not most of the time.

Against common sense, it is well known that certain seemingly self-destructive practices are encouraged by evolution and natural selection. This is because they enhance the probabilities of mating. The peacock's large feathers are cumbersome, but they help him attract his mate. The deliberate use of a head to contact the ball is possibly in this way a signal that someone has a strong, powerful cranium and could improve evolutionary fitness. Furthermore, the nimble use of feet is a subtle signal of dexterity and control.

Furthermore we see in football what it means to be alive. Players play with minimal protection. This is a return to the old times where passions flared and people fought uninhibited. Football is a civilized metaphor for that action. Without protection, or any barrier (such as helmets and the like) between players and the referee, players are free to express their emotions for everyone to see.

This passion is why football is the world's game. Playing football is not an expression of deep thought; it is a return to our emotional roots, our passion, our conflicts; what it means not just to be human, but to be a living being.