Algorithmic beauty is the same as algorithmic usefulness. Beauty is simplicity, beauty is elegance, and beauty is efficiency. This blog is about solving problems of all kinds.
Algorithms are much more than snippets of computer code. A computer follows algorithms created by a programmer, but algorithms show up in all facets of life. Creating an algorithm is the process of breaking a problem down into small steps in such a way as to always solve the problem, no matter what the input is. There are often many ways to solve a given problem. But some algorithms will prove more useful, more beautiful than others.
Consider my son, who is almost 3. A few months ago he was taken with the challenge of stacking blocks. But the blocks were different sizes, so only certain stacking orders would work, the biggest block had to go at the bottom and so on. Yet this constraint was not obvious to him, so his strategy was one of “brute force”. He would pick up a block and attempt to stack it. If it didn’t work, he would pick a different block. If he reached a point where there were no blocks he could stack, but still blocks that remained, he would start over with a new, randomly chosen block at the bottom.
He is enumerating through all permutations, sorting the blocks by largest to smallest by trying every combination until he finds the one that is correct. If he had 3 blocks we labeled with numbers (3 being the largest), he would have the following combinations to go through (assuming he never attempted the same combo twice, which he of course did).
- 1,2,3
- 1,3,2
- 2,1,3
- 2,3,1
- 3,1,2
- 3,2,1
These six choices are manageable with such a small data set. However, this kind of algorithm grows quickly untenable. If he had 10 blocks, for example, he would have 3,628,800 combinations to try before finding the correct one. If he had 100 blocks, he would have more combinations to try than there are atoms in the entire universe. The important consideration is that as the input grows in size, the number of operations required to solve the problem grows according to a mathematical function. In this case it is “n!” (the number you get by multiplying all numbers from 1 to n). This is the “order” of the algorithm, the overall efficiency, and this is quantifiable beauty, and this algorithm is rather homely.
If we added an extra step after the block tower was built (say, toppling the tower with a ruthless cackle), that step wouldn’t really matter when considering the overall efficiency. It would seem to change the order to “n! + 1”, but the 1 becomes increasingly insignificant as the input grows in size. With 3 blocks, it is 1/7 of the steps, but with 10, it is infinitesimal. So, such scalar values are dropped from the equation and we consider this algorithm to still have an order of “n!”.
There are many other (more efficient) strategies he could take to sort his blocks. He could look through the un-stacked blocks for the largest remaining, and remove it and put it in place. Or he could separate the blocks into piles of like sizes. The first pass we make 2 piles, one for 1-5, one for 6-10. The second pass we divide each of the sub-piles into smaller sub piles, and so on until the blocks are all in order. These are other established sorting algorithms that I will discuss in future posts.
He also might need to consider the space it takes to perform. In the living room he can spread the blocks out and consider them individually, but what if he tried to stack the blocks in his toddler bed, with much less staging ground? He would need other algorithms, other strategies. Likewise in algorithmatics, we might need to consider the amount of computer memory an algorithm might take, this is another dimension of efficiency, another shade of beauty.
An algorithm is simply a fool proof method of accomplishing a certain task, and they are everywhere. Driving directions, recipes, kicking a soccer ball, repairing a bicycle are all algorithmic tasks. The algorithms used by computer programs are usually more general, they accomplish a task based on a specific input. It wouldn’t be useful to write a program to give you directions from my house to my office, rather we need a program to give directions from any point to any other point, like a GPS device does. These computers use an algorithm, taking into consideration things like speed limits, road construction, toll road preferences, to find the fastest way to get from point A to B. Imagine if your GPS had to find every possible way to get from one point in order to find the fastest! Rather the algorithm has to be carefully crafted to find the fastest route in an efficient, elegant, beautiful way.
This is the elegance that interests me, and the primary focus of this blog. I will also discuss probability, mathematics, SQL, programming, etc, I’ll include code snippets of SQL, C#, Java, Javascript as they seem useful. I’ll try to write in plain language, but in all likelihood most posts will be technical in nature. What I’m really after are interesting problems and their solutions, and to that end I welcome discussion. If you have a better solution or see an error in mine, or if there is a problem you find interesting that you’d like to share, please do.