Browse Prior Art Database

SAME MODIFIED ALGORITHMS FOR DIJKSTRA`S LONGEST UPSEQUENCE PROBLEM

IP.com Disclosure Number: IPCOM000128178D
Original Publication Date: 1980-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 9 page(s) / 27K

Publishing Venue

Software Patent Institute

Related People

ROBERT B.K. DEWAR: AUTHOR [+4]

Abstract

Two modified merge algorithms for the longest upsequence problem are presented. The algorithms take advantage of natural runs in the input sequence and have a worst case 0(nlogn) time complexity when appropriate merging techniques are used, but can be linear if long runs are present in the sequence. The first algorithm is logically equivalent to Dijkstra's algorithm; the second algorithm is based on the first one but uses a different merging technique. Concluding remarks describe how these results evolved out of our work in programming by transformation.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 19% of the total text.

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

SAME MODIFIED ALGORITHMS FOR DIJKSTRA`S LONGEST UPSEQUENCE PROBLEM

BY ROBERT B.K. DEWAR SUSAN M. MERRITT and MICHA SHARIR

41 October 19-80~ REPORT NO. 026 This material is based upon work supported by the National Science Foundation under Grant No. MCS-8004349.

Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors) and do not necessarily reflect the views of the National Science Foundation. Some Modified Algorithms for Dijkstra'a Longest Upsequence Problem

Robert B.K. Dewar, Susan M. Merritt and Micha Sharir

Computer Science Department Courant Institute New York University

October 1980

ABSTRACT:

Two modified merge algorithms for the longest upsequence problem are presented. The algorithms take advantage of natural runs in the input sequence and have a worst case 0(nlogn) time complexity when appropriate merging techniques are used, but can be linear if long runs are present in the sequence. The first algorithm is logically equivalent to Dijkstra's algorithm; the second algorithm is based on the first one but uses a different merging technique. Concluding remarks describe how these results evolved out of our work in programming by transformation.

Longest unseguence problem

Given a sequence of n integers, an upsequence is a subsequence which is ordered in nondecreasing order. A subsequence is any subset of the original sequence in which the original order is retained (hence there are 2**n possible subsequences.)

The problem we consider is: Give an algorithm which, given a sequence, will return the length of its longest upsequence. (Note that there may be more than one longest upsequenc.e of the same length.)

Dijkstra's algorithm

' Dijkstra's algorithm [Di] examines elements in the original sequence from left to right. When a 'next' element is examined it is inserted into what Dijkstra denotes as the m array (consisting of minimum rightmost elements of upsequences of length 1,2,...). (Here we will refer to the 'm array' as the 'target sequence'.) New sequence elements x are inserted into the target sequence either by being added to the right end (if x is larger than the rightmost element of the partial

New York University Page 1 Dec 31, 1980

Page 2 of 9

SAME MODIFIED ALGORITHMS FOR DIJKSTRA`S LONGEST UPSEQUENCE PROBLEM

target sequence) or by 'bumping' an element already in the target sequence. If x = A[n] is the next element of the input sequence, Page .2

the heart of the Dijkstra algorithm is:

(Equation Omitted)

Dikstra uses a binary search technique to determine j, which makes the complexity of his algorithm 0(nlogn).

First Modified Merge Algorithm

The algorithm presented here, although logically equivalent to Dijkstra's algorithm, uses a fresh and more efficient approach. Rather than examining the input sequence element by element in a left to right manner, the algorithm proceeds as follows:

1) Divide the inp...