ISSN:
1432-0525
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary Using the techniques of “specification and transformation by parts”, algorithms are derived for the longest upsequence problem. First Dijkstra's algorithm and then two new modified merge algorithms are derived and presented in detail. The merge algorithms take advantage of natural runs in the input sequence and have a worst caseO(n logn) time complexity when appropriate merging techniques are used, but can be linear if long runs are present in the sequence. The first merge algorithm is logically equivalent to Dijkstra's algorithm; the second algorithm is based on the first one but uses a different merging technique. Expository remarks describe related results which evolved out of our work in programming by transformation; in particular, parallels are drawn between algorithms for the longest upsequence problem and algorithms for sorting.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00625277
Permalink