A software engineering perspective on algorithmics

Analgorithm componentis an implementation of an algorithm which is not intended to be a stand-alone module, but to perform a specific task within a large software package or even within several distinct software packages. Therefore, the design of algorithm components must also incorporate software-engineering aspects. A key design goal is adaptability. This goal is important for maintenance throughout a project, prototypical development, and reuse in new, unforseen contexts. From a theoretical viewpoint most algorithms apply to a range of possible use scenarios. Ideally, each algorithm is implemented by one algorithm component, which is easily, safely, and efficiently adaptable to all of these contexts.Various techniques have been developed for the design and implementation of algorithm components. However, a common basis for systematic, detailed evaluations and comparisons in view of therealpractical needs is still missing. Basically, this means a set of concrete criteria, which specify what sort of adaptability isreallyrequired in practice, and which are well-justified by convincing, representative use scenarios.This paper is intended to be a first “milestone” on the way towards such a system of criteria. We will present a set of concrete goals, which are general and problem-independent and might appear ubiquitously in the algorithmic realm. These goals are illustrated, motivated, and justified by an extensive requirements analysis for a particular algorithm from a particular algorithmic domain: Dijkstra's algorithm for shortest paths in networks.Clearly, the field of algorithmics might be too versatile to allow a comprehensive, yet concise set of precise, justified criteria. Even a domain as restricted as graph and network algorithms includes aspects that are not fully understood. The analysis will include a discussion of the limits of the case study and the scope of the goals. The case study was chosen because it seems to be close to the “boderline” between the aspects that are well understood and the aspects that are not. Hence, this example may well serve as an“acid test” for programming techniques in view of the state of the art.