Online Algorithms and Range Qeury Techniques for Some Constrained Maximum-Sum and Maximum-Average Segment Problems
Date Issued
2005
Date
2005
Author(s)
Chen, Kuan-Yu
DOI
zh-TW
Abstract
The range minima query problem, RMQ for short, is to preprocess a sequence of real
numbers A[1...n] for subsequent queries of the form: ``Given indices i, j, what is the
index of the minimum value of A[1...n]?" This problem is shown to be equivalent to the
LCA problem in which a tree is preprocessed for answering the lowest common ancestor
of two nodes. It is also shown that both the RMQ and LCA problem can be solved
optimally under the RAM model.
Motivated by some biological string problems, the first part of the paper considers a similar
query problem, in which we wish to answer queries of the form: ``Given indices i, j,
where is the maximum-sum segment of A[1...n]?" By showing the equivalence between
this problem and RMQ, we obtain a linear preprocessing time and constant query time
solution. We extend this result to solve in linear time three biological string problems
related to maximum-sum segments. These variations on the basic theme demonstrate
the utilities of the techniques developed in this thesis.
As for the second part of the paper, we devise two linear time online algorithms for
the following biological string problems: ``Given a sequence of real numbers, locate the
longest and shortest segment satisfying a sum or an average constraint."
Our algorithms improve on previous algorithms by providing the capability of handling data string inputs.
Subjects
區域查詢
最大總和
最大平均值
maximum-sum
maximum-average
RMQ
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-94-R92922047-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):9bc74ae94b711a515d01fa4bb8bef9e1