Præsentere Artiklen, Selecting Sums in Arrays

Aktivitet: Tale eller præsentation - typerForedrag og mundtlige bidrag

Se relationer på Aarhus Universitet

Allan Grønlund - Foredragsholder

  • Datalogisk Institut
 In an array of $n$ numbers each of the $\binom{n}{2}+n$ contiguous
  subarrays define a sum.  In this paper we focus on algorithms for
  selecting and reporting maximal sums from an array of numbers. First,
  we consider the problem of reporting $k$ subarrays inducing the $k$
  largest sums among all subarrays of length at least $l$ and at most
  $u$. For this problem we design an optimal $O(n+k)$ time algorithm.
  Secondly, we consider the problem of selecting a subarray storing the
  $k$'th largest sum. For this problem we prove a time bound of
  $\Theta(n \cdot \max\{1,\log k/n\})$ by describing an algorithm with this
  running time and by proving a matching lower bound.  Finally, we
  combine the ideas we used and obtain an $O(n\cdot \max\{1,\log k/n\})$ time
  algorithm for selecting a subarray storing the $k$'th largest sum
  among all subarrays of length at least $l$ and at most $u$.


Emneord: Algorithms, Data Structures
15 dec. 2008

Begivenhed (Konference)

Titel Symposium on Algorithms and Computation
Dato15/12/200815/12/2008
EmneAlgorithms and Data Structures
ByGold Coast
LandAustralien

ID: 14696241