Algorithmic Problem Solving

This chapter collects together the basic principles of algorithm design. The main focus is the design of iterative algorithms. These are algorithms that achieve a given task by repeatedly (‘iteratively’) executing the same actions in a so-called loop. We use three problems to illustrate the method. The first is deliberately very simple, the second and third are more challenging.

The principles themselves have already been introduced individually in earlier chapters. In summary, they are:

Sequential (De)composition   Sequential decomposition breaks a problem down into two or more subproblems that are solved in sequence. The key creative step in the use of sequential decomposition is the invention of intermediate properties that link the components.

Case Analysis   Case analysis involves splitting a problem into separate cases which are solved independently. The creative step is to identify an appropriate separation: avoiding unnecessary case analysis is often crucial to success.

Induction   Induction entails identifying a class of problems each of which has a certain ‘size’ and of which the given problem is an instance. The solution to any problem in the class is to repeatedly break it down into strictly smaller subproblems together with a mechanism for combining the solutions to the subproblems into a solution to the whole problem. Problems of the smallest size cannot be broken ...