When

Start: 11/14/2016 - 4:15pm

End : 11/14/2016 - 5:15pm

End : 11/14/2016 - 5:15pm

Category

Applied Math Seminar

Speaker

Ho-Kwak Dai (CMC; Oklahoma State University)

Abstract

Efficient algorithms for finding multiple contiguous subsequences of a

real-valued sequence having large cumulative sums, in addition to its

combinatorial appeal, have widely varying applications such as in textual

information retrieval and bioinformatics. A maximum contiguous subsequence

of a real-valued sequence is a contiguous subsequence with the maximum

cumulative sum. A minimal maximum contiguous subsequence is a minimal

contiguous subsequence among all maximum ones. We present an overlapping

domain-decomposed parallel algorithm on cluster systems with Message Passing

Interface that finds all successive minimal maximum subsequences of a random

sample sequence from a normal distribution with negative mean. Our study

employs the theory of random walk to derive a probabilistic length upper

bound for the common intersection of overlapping subsequences, which is

incorporated in the algorithm to facilitate the concurrent computation of

all minimal maximum subsequences in hosting processors.

*On sabbatical leave from Computer Science Department, Oklahoma State

University, Stillwater, Oklahoma 74078. Sincere thanks to Claremont McKenna

College for its hospitality.

Where

Emmy Noether Room
Millikan 1021 Pomona College