Engineering is Fun!

Thinking like a Computer – Algorithms

An algorithm is a description of a process that operates on a given input to produce a desired output. This definition is both very general and very similar to the description of what a computer does. The difference is that an algorithm is just a description of a process. It does not necessarily have to run on a computer. But algorithms are also sequences, and thus they are very well suited to be executed by a computer program.

A typical example of an algorithm would be a sorting algorithm. It is a description how to bring a set of unordered items into a a given order. Remember the problem sorting the numbered socks from the last section? The solution to this problem would be a sorting algorithm. The sorting algorithm describes how to bring the socks into the correct order. If you follow these instructions, you can sort the socks manually. But you can also program your computer to do it for you. The algorithm stays the same – it is just a description of the process.

There are many kind of algorithms for all different types of problems out there. Sorting elements is a problem that has many applications, and so there are many different sorting algorithms out there. All of them are very well described and you can find many ready implementations. An algorithm is like a recipe for problem solving. And because there are so many similar problems programmers have to solve every day, there are a lot of different algorithms available. If you find yourself stuck with a problem, check whether there is an algorithm for it. There are algorithms for compressing data, encrypting messages, calculating the distance between objects or even recognizing pictures with cats on them.

If you have multiple algorithms that can solve the same problem, which one should you choose? It depends on your constraints. An important constraint is the time in which the computer has to solve the problem. If you have two algorithms to solve your problems, you would choose the one that needs less time to produce the result. An algorithm usually finishes faster if it needs less operations. An operation is every step in your sequence, like reading or writing from memory or comparing two values. Each of these steps takes a little bit of time to finish. So the less steps you have, the faster you get the result.

The amount of operations an algorithm needs depends on the size of the input data. A measure to easily compare algorithms is the computational complexity. It describes how fast the number of operations and thus the execution time of an algorithm increase with the input size. This is a bit theoretical, but it becomes much clearer with the Big O notation. In the description of an algorithm, you will find a value like O(n) or O(n2). To compare these two, just imagine this like a function that you draw in a coordinate system. O(n) is a linear function, O(n2) is a quadratic function. You can easily see that if you double the input, than the first algorithm will need double the execution time, but the second will need four times. So the first algorithm is clearly better in this regard.

But don’t just look out for the complexity of the algorithm. It does not help you to have the fastest algorithm if it does not fit into the memory of your computer! In practice, you often have the tradeoff between execution time and memory consumption. So take your time to understand the ressources needed by the solution you choose.

This advice is not only true for embedded systems, where CPU speed and memory are very limited. It is also important for large scale servers. Imagine Facebook’s or Google’s data centers. If you use an algorithm that saves just a few percent of memory, it is possible that you need a few servers less and thus save a lot of money!

Computer scientists and mathematicians like to think a lot about algorithms and find the limits about what a computer can calculate. Yes, there are limits. There are problems which cannot be solved even by the fastest computers during our lifetime. This might sound bad, but it also has an upside: Modern cryptology is based on problems that are so hard to solve that you cannot do it with a computer. Most likely, you will not meet these limits, but it is important to keep in mind that they exist. If you really want to learn more about it, you can make yourself familiar with the concept of the Turing Machine which is used in Computability Theory.

In practice, you should keep in mind that there are algorithms for many problems that you might encounter. Don’t try to reinvent the wheel if there is already a well-described algorithm to solve your problem. But you need to know how to decide which algorithm is the best for your problem.

I hope you enjoyed this article. If you have any questions or comments, please contact me.