SB CSE 675
Fall 2000
Program Transformation and Program Analysis
Annie Liu
Exercises 8
Handout E8
Nov. 16, 2000
Due Nov. 22

Optimizing Aggregate Array Computations. (Due at class time next Wednesday.)

Problem 1. Sampled data processing

Many real-time engineering experiments need to process a continuous sequence of sampled input. Often, to reduce noise in the input data, at each data point, an average of its neighbors is taken. The following example code is often seen to compute the sums: given array a[1..n], array b[1..n-9] is b[i]=a[i]+a[i+1]+...+a[i+9] for each i.

(1)  for i: = 1 to n-9 do
(2)    b[i] := 0;
(3)    for j: = 0 to 9 do
(4)      b[i] := b[i] + a[i+j];

a. For the aggregate array computation formed by the inner loop, what is the contributing set?

b. What are the update operations to this aggregate array computation?

c. What are the decrement set and increment set?

d. What is the incrementalized code for

(2)'    b[i+1] := 0;
(3)'    for j: = 0 to 9 do
(4)'      b[i+1] := b[i+1] + a[i+1+j];

e. What is the optimized program?

Problem 2. Minimum-sum section problem

Given an array a[1..n] of numbers, where n>=1. A minimum-sum section of a is a non-empty sequence of adjacent elements whose sum is a minimum. A naive algorithm, such as the one below, takes O(n^3) time to compute such a minimum in m.

(1)  min := a[1];
(2)  for i := 1 to n do
(3)    for j := i downto 1 do
(4)      s :=0;
(5)      for k := i to j do
(6)        s := s + a[k]
(7)      m := min(m,s)
Give a linear-time algorithm for this problem. You don't need to give a detailed derivation. The result could be as simple as 5 lines: a loop with two assignments for initialization before the loop and two assignments for incremental updates inside the loop.