Before Danny Hillis became very rich as the developer of massively parallel supercomputers, he was an undergraduate at MIT who suffered from an excruciating problem. It was his roommate. In the morning, his roommate would reach into his clean laundry hamper, pull out one sock at random, then pull out a second sock. If it didn’t match, he would throw the second sock back in and grab randomly again for another sock. This would be upsetting for anyone, and especially for a logical person such as Hillis: clearly there have to be better ways of finding matching pairs of clean socks. But how much better?

This question is at the heart of the study of algorithms, the formal procedures that we use to do things. Simple algorithms have been around for ages. When you follow a recipe, for example, you’re following an algorithm. But the field really took off with the growth of digital technology in the past few decades, for almost all tasks that computers perform involve going through the steps in increasingly complex algorithms.

…

Subscribe to read the full article