A software engineering perspective on algorithmics

Authors
Citation
K. Weihe, A software engineering perspective on algorithmics, ACM C SURV, 33(1), 2001, pp. 89-134
Citations number
55
Categorie Soggetti
Computer Science & Engineering
Journal title
ACM COMPUTING SURVEYS
ISSN journal
03600300 → ACNP
Volume
33
Issue
1
Year of publication
2001
Pages
89 - 134
Database
ISI
SICI code
0360-0300(200103)33:1<89:ASEPOA>2.0.ZU;2-Y
Abstract
An algorithm component is an implementation of an algorithm which is not in tended to be a stand-alone module, but to perform a specific task within a large software package or even within several distinct software packages. T herefore, the design of algorithm components must also incorporate software -engineering aspects. A key design goal is adaptability. This goal is impor tant for maintenance throughout a project, prototypical development, and re use in new, unforeseen contexts. From a theoretical viewpoint most algorith ms apply to a range of possible use scenarios. Ideally, each algorithm is i mplemented by one algorithm component, which is easily, safely, and efficie ntly 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 eva luations and comparisons in view of the real practical needs is still missi ng. Basically, this means a set of concrete criteria, which specify what so rt of adaptability is really required in practice, and which are well-justi fied 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 gene ral and problem-independent and might appear ubiquitously in the algorithmi c realm. These goals are illustrated, motivated, and justified by an extens ive requirements analysis for a particular algorithm from a particular algo rithmic domain: Dijkstra's algorithm for shortest paths in networks. Clearly, the field of algorithmics might be too versatile to allow a compre hensive, yet concise set of precise, justified criteria. Even a domain as r estricted as graph and network algorithms includes aspects that are not ful ly 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 "borderline" between the aspects that are well un derstood and the aspects that are not. Hence, this example may well serve a s an "acid test" for programming techniques in view of the state of the art .