Principles of Algorithm Design

Why do we want to study algorithm design? There are of course many reasons, and our motivation for learning something is very much dependent on our own circumstances. There are without doubt important professional reasons for being interested in algorithm design. Algorithms are the foundations of all computing. We think of a computer as being a piece of hardware, a hard drive, memory chips, processors, and so on. However, the essential component, the thing that, if missing, would render modern technology impossible, is algorithms.

The theoretical foundation of algorithms, in the form of the Turing machine, was established several decades before digital logic circuits could actually implement such a machine. The Turing machine is essentially a mathematical model that, using a predefined set of rules, translates a set of inputs into a set of outputs. The first implementations of Turing machines were mechanical and the next generation may likely see digital logic circuits replaced by quantum circuits or something similar. Regardless of the platform, algorithms play a central predominant role.

Another aspect is the effect algorithms have in technological innovation. As an obvious example, consider the page rank search algorithm, a variation of which the Google search engine is based on. Using this and similar algorithms allows researchers, scientists, technicians, and others to quickly search through vast amounts of information extremely quickly. This has a massive effect on the rate at which new research can be carried out, new discoveries made, and new innovative technologies developed.

The study of algorithms is also important because it trains us to think very specifically about certain problems. It can serve to increase our mental and problem solving abilities by helping us isolate the components of a problem and define relationships between these components. In summary, there are four broad reasons for studying algorithms:

1. They are essential for computer science and intelligent systems.
2. They are important in many other domains (computational biology, economics, ecology, communications, ecology, physics, and so on).
3. They play a role in technology innovation.
4. They improve problem solving and analytical thinking.

Algorithms, in their simplest form, are just a sequence of actions, a list of instructions. It may just be a linear construct of the form do x, then do y, then do z, then finish. However, to make things more useful we add clauses to the effect of, x then do y, in Python the if-else statements. Here, the future course of action is dependent on some conditions; say the state of a data structure. To this we also add the operation, iteration, the while, and for statements. Expanding our algorithmic literacy further we add recursion. Recursion can often achieve the same result as iteration, however, they are fundamentally different. A recursive function calls itself, applying the same function to progressively smaller inputs. The input of any recursive step is the output of the previous recursive step.

Essentially, we can say that algorithms are composed of the following four elements:

• Sequential operations
• Actions based on the state of a data structure
• Iteration, repeating an action a number of times
• Recursion, calling itself on a subset of inputs