Algorithm engineering

Algorithm Engineering focuses on the design, analysis, implementation, optimization, profiling and experimental evaluation of computer algorithms, bridging the gap between algorithm theory and practical applications of algorithms in software engineering.[1] It is a general methodology for algorithmic research.[2]

Origins

In 1995, a report from an NSF-sponsored workshop "with the purpose of assessing the current goals and directions of the Theory of Computing (TOC) community" identified the slow speed of adoption of theoretical insights by practitioners as an important issue and suggested measures to

But also, promising algorithmic approaches have been neglected due to difficulties in mathematical analysis.[2]

The term "algorithm engineering" was first used with specificity in 1997, with the first Workshop on Algorithm Engineering (WAE97), organized by Giuseppe F. Italiano.[4]

Difference to Algorithm Theory

Algorithm engineering does not intend to replace or compete with algorithm theory, but tries to enrich, refine and reinforce its formal approaches with experimental algorithmics (also called empirical algorithmics).

This way it can provide new insights into the efficiency and performance of algorithms in cases where

Methodology

Some researchers describe algorithm engineering's methodology as a cycle consisting of algorithm design, analysis, implementation and experimental evaluation, joined by further aspects like machine models or realistic inputs. They argue that equating algorithm engineering with experimental algorithmics is too limited, because viewing design and analysis, implementation and experimentation as separate activities ignores the crucial feedback loop between those elements of algorithm engineering.[2]

Realistic Models and Real Inputs

While specific applications are outside the methodology of algorithm engineering, they play an important role in shaping realistic models of the problem and the underlying machine, and supply real inputs and other design parameters for experiments.[2]

Design

Compared to algorithm theory, which usually focuses on the asymptotic behavior of algorithms, algorithm engineers need to keep further requirements in mind: Simplicity of the algorithm, implementability in programming languages on real hardware, and allowing code reuse. Additionally, constant factors of algorithms have such a considerable impact on real-world inputs that sometimes an algorithm with worse asymptotic behavior performs better in practice due to lower constant factors.

Analysis

Some problems can be solved with heuristics and randomized algorithms in a simpler and more efficient fashion than with deterministic algorithms. Unfortunately, this makes even simple randomized algorithms difficult to analyze because there are subtle dependencies to be taken into account.[2]

Implementation

Huge semantic gaps between theoretical insights, formulated aglorithms, programming languages and hardware pose a challenge to efficient implementations of even simple algorithms, because small implementation details can have rippling effects on execution behavior. The only reliable way to compare several implementations of an algorithm is to spend an considerable amount of time on tuning and profiling, running those algorithms on multiple architectures, and looking at the generated machine code.[2]

Experiments

See: Experimental algorithmics

Application Engineering

Implementations of algorithms used for experiments differ in significant ways from code usable in applications. While the former prioritizes fast prototyping, performance and instrumentation for measurements during experiments, the latter requires thorough testing, maintainability, simplicity, and tuning for particular classes of inputs.[2]

Algorithm Libraries

Stable, well-tested algorithm libraries like LEDA play an important role in technology transfer by speeding up the adoption of new algorithms in applications. Such libraries reduce the required investment and risk for practitioners, because it removes the burden of understanding and implementing the results of academic research.

Conferences

Some annual conferences have been held for algorithm engineering:

The 1997 Workshop on Algorithm Engineering (WAE'97) was held in Venice (Italy) on September 11–13, 1997. The Third International Workshop on Algorithm Engineering (WAE'99) was held in London, UK in July 1999.[6] The first Workshop on Algorithm Engineering and Experimentation (ALENEX99) was held in Baltimore, Maryland on January 15–16, 1999.[7] It was sponsored by DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science (at Rutgers University), with additional support from SIGACT, the ACM Special Interest Group on Algorithms and Computation Theory, and SIAM, the Society for Industrial and Applied Mathematics.[7]

References

  1. 1 2 "Algorithm Engineering", Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, web: http://wwwusers.di.uniroma1.it/~finocchi/papers/EATCSBullet.ps
  2. 1 2 3 4 5 6 7 "Algorithm Engineering – An Attempt at a Definition", Peter Sanders, web: http://algo2.iti.kit.edu/documents/definition.pdf
  3. ↑ "Emerging Opportunities for Theoretical Computer Science", Aho, Johnson, Karp, Kosaraju, McGeoch, Papadimitriou, web: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9160
  4. ↑ Workshop on Algorithm Engineering
  5. ↑ "Towards a Discipline of Experimental Algorithmics", Bernard M. E. Moret, web: http://infoscience.epfl.ch/record/97865/files/dimacs_algorithmics.pdf
  6. ↑ Algorithm engineering: 3rd International Workshop, Jeffrey Scott Vitter, Christos D. Zaroliagis, 1999, web: BGoogle-sC.
  7. 1 2 "Workshop on Algorithm Engineering and Experimentation" (overview), JHU.edu, 1999, web: JHU-ALENEX99.

External links

This article is issued from Wikipedia - version of the Thursday, April 28, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.