SB CSE 675
Program Transformation and Program Analysis
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; (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.