Computer science gives us a better opportunity to test ideas than, say, particle physics. The ability to experiment so easily is a major part of the appeal for

Computer science gives us a better opportunity to test ideas than, say, particle physics. The ability to experiment so easily is a major part of the appeal for many of us. > Even the stereotypical "impractical" research algorithms > (with efficient complexity but huge constants) are > implemented. Well, they're all Turing machines, but you're not going to find any video processing algorithms that were implemented on a 4K Altair so let's not go too far. It's interesting to consider a given novel idea and wonder how far back in time it would have been possible to implement it in a practical way and how much further back in time it would have been useful simply to know how it works. Let me pick a concrete example that we are all familiar with: Hashing. Hashing and hash lookup algorithms have been around a long time. It's an area that people might expect would have been exhausted of significant new ideas long ago. Not so! Cuckoo hashing was invented in 2001 and gives us dramatically more efficient use of memory at a slight performance cost. It can make the difference between a hash table that fits in memory and one that doesn't so it's a meaningful advance. Cuckoo hashing could have been implemented on a 4k Altair and it would have been useful there. But no one had the idea then. But wait-- It gets stranger! Cuckoo hashing was literally under our noses and somehow no one saw it! It is a variation of set associative hashing which is what most CPUs had already been doing in their caches for years. It's not exactly the same algorithm but if you check you'll see it's so close the distinctions are minor. Fascinating, isn't it? Here is an important algorithm that was actually live and running in hardware yet no one considered building it in software for a long time.