Access Restriction

Author Kolm, Å. ♦ Dahlstrand, T.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Dual problem ♦ Dual simplex method ♦ Linear programming ♦ Primal problem
Abstract In his Certification of Algorithm 245 [1], Ralph L. London exhibits a common confusion between an algorithm, its representation, and its implementation on a processor—a code. In the present state of the art we can attempt, in general, to prove an algorithm and to test a code. For example, London states that “… the algorithm TREESORT 3 [2] is proved to perform properly its claimed task of sorting an array M[1:n] into ascending order.” While this is true of the algorithm, it is not true of the code unless we place restrictions on the array elements. The trouble arises in this example from the finite precision of processors; the Boolean expression A ≥ B (real A, B) will usually be implemented as A - B ≥ 0, which can fail due to floating point overflow or underflow.
Description Affiliation: Information Processing Department, ASEA, Västerås, Sweden (Kolm, Å.; Dahlstrand, T.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 14
Issue Number 1

Open content in new tab

   Open content in new tab
Source: ACM Digital Library