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.