The Art Gallery Guardian

Sum of sparse array in linear time


Let . Define . We want to represent an -dimensional array. Assume and are both -dimensional arrays of size and one have non-zero elements one have non-zero elements. The following operations should be supported.

  1. creates a new sparse array , such that . This is the circshift operation in matlab. Running time should be .
  2. Similarly, we can define , such that , if is outside the range, we have instead.
  3. returns a sparse array such that in time.
  4. output all elements with associated coordinates in in time.
  5. create a new sparse array with size and one element initialized at position.

We create a sparse list with dimension slices, and the lower dimension slices can be handled inductively. All we need to do is to implement sparse list. The list should store the position and value pairs ordered by position. Sum can be done with a merge operation. circshift go though all elements one by one and update the position, and then rotate the list so the smallest position is in the beginning.

This data structure can be useful output sensitive dynamic programming problems. For example, multidimensional subset sum have a simple recursive solution.

  1. Input
  2. .
  3. For from to , .
  4. Return

The running time is , where is the final output, since is a shift, and union is just a sum. Using circshift, it can produce a output sensitive algorithm for subset sums in finite abelian groups.

Posted by Chao Xu on .
Tags: Algorithm.