What is Algorithmic Problem Solving?

Our use of the term “algorithmic problem solving” is deliberately ambiguous. On the one hand, it can be read as “algorithmic-problem solving”; this means solving problems that require the formulation of an algorithm for their solution. On the other hand, it can be read as “algorithmic problem-solving”; this means exploiting what has been learned from the experience of developing computer software over the last 50 years that has helped us to hone our problem-solving skills.

The formulation of algorithms has always been an important element of problem-solving but, in the past, the algorithm has seldom been the focus of attention. The fact that automation is an ever-present feature of our daily lives (in the developed world) means that we must devote more and more effort on improving our skills in algorithmic problem-solving. Algorithms are the end-product of the problem-solving process and it is imperative that they are made explicit and are carefully studied.

Over the last 50 years, much effort has gone into methodologies for algorithm design. A particular focus has been on so-called “correct-by-construction” design techniques. These techniques involve first formulating a mathematical specification of what the algorithm is required to compute and then developing the algorithm in a way that guarantees that it meets its specification. The process of formulating a specification involves abstraction from so-called “real-world” problems; it helps to eliminate ambiguity and clarify the true nature of the problem being tackled. Correct-by-construction is a systematic way of designing algorithms using the specification as a blueprint; it is a pre-hoc design process quite different from the post-hoc process used to “debug” computer software. Of course, testing of all software is a vital part of its design, even when correct-by-construction techniques have been used: testing may reveal flaws in the specification as well as providing an independent check on the validity of the software (an indispensable process in all problem solving).

Roland Backhouse’s book on Algorithmic Problem Solving introduces the principles underlying correct-by-construction design techniques. Problem solving is not easy. Don’t confuse problem solving with the verification of existing solutions; construction is much harder than verification! So the examples are often challenging and require careful study.