Abstract
A formal derivation is presented of an efficient algorithm for computing the "sums" of all segments, of a given length, of a sequence. Here, "sums" refers to the continued application of a binary operator of which associativity is the only known property. Recurrence relations are used to separate two concerns, viz. characterization of the values to be computed and choosing the order in which these values will be computed.
Original language | English |
---|---|
Pages (from-to) | 297-299 |
Journal | Information Processing Letters |
Volume | 36 |
Issue number | 6 |
DOIs | |
Publication status | Published - 1990 |