Minsegsumtwodim

Minsegsumtwodim

Remark about notation By way of experiment I shall denote functional application by an infix period; it has the highest binding power of all and is (as usual) left-associative. By way of further experi- ment, I shall also use that period for subscription. (End of Remark about notation.)

This note is a sequel to EWD897, in which the one-dimensional "minsegsum" is solved in linear time.

The functional specification for minsegsumtwodim is

[\left\lbrack {M,N : \operatorname{int}\left{ {M ≥ 0 ∧ N ≥ 0}\right} }\right\rbrack ]

$\therefore C\left( {m,n : 0 ≤ m < M ∧ 0 ≤ n < N}\right)$ array of int

; minsegsumtwodim

R: x = (MIN m0,m1,n0,n1: 0≤m0≤m1≤M

$0 ≤ n 0 ≤ n 1 ≤ N$ :

(S m, n: $m0≤ m < m1∧ n0≤ n < n1$ : C.m.n))}

31

21

in which (as usual) the constants of the environment are declared in the outer block.

Remark. For $M = 1$ , the specification of minsegsum-twodim reduces to that of aforementioned one-dimensionai minsegsum. (End of Remark.)

We remark that in MIN the ranges have been given including the bounds because, without further con- ventions, the minimum over an empty range is undefined. In S the ranges exclude the upper bound, summation over the empty range being defined to yield 0 (i.e. the identity element of the addition).

Since summations over empty ranges ( $m0 = m1$ $v n0 = n!$ ) are included and all yield 0 , we can take them out of the range for MIN and rewrite $R$

R: x = 0 min (MIN m0, m1, n0, n1: 0 ≤ m0 < m1 ≤ M ∧

0 ≤ n 0 < n 1 ≤ N:

(∑m,n:m0≤m<m1∧n0≤n<n1:C.m.n))

provided we extend the definition of MIN with a suitable identity element if its range is empty; from our last form of R we see that 0 will do in this context.

We know that, for $M = 1$ ,there exists a solution linear in $N$ (and we would like our solution for minsegsumtwodim to reduce to that linear one if $M = 1$ ). In a rectangle with two rows, however,the solution for minsegsumtwodim has little relation to the solutions for minsegsum in the individual rows,as is shown by the following examples:

• for each rectangle we give the number of rightmost columns that realize the minsegsums and min-segsumtwodim respectively.

<table><tr><td colspan="3">rectangle</td><td>minsegsum</td><td>minsegsumtwodim</td></tr><tr><td>(i)</td><td>-2</td><td>+3</td><td>-6</td><td>1</td></tr><tr><td></td><td>+1</td><td>-3</td><td>-6</td><td>2</td></tr><tr><td>(ii)</td><td>+2</td><td>+1</td><td>-5</td><td>1</td></tr><tr><td></td><td>-1</td><td>-2</td><td>-2</td><td>3</td></tr><tr><td>(iii)</td><td>+4</td><td>-1</td><td>-4</td><td>2</td></tr><tr><td></td><td>-3</td><td>+2</td><td>-6</td><td>3</td></tr></table>

The moral of the above observation seems to be that if we wish to apply minsegsum computations in the $N$ -direction, they can share in the $M$ -direction little more than the summation. In the following this will be made more precise.

Our next step is to rewrite R in terms of nested MIN's and S's. (At this stage, the reader is invited to convince himself of the correctness of my rewriting and urged to shelve for the time being the question why R is rewritten this way. He is, however, welcome to observe that we have concentrated the quantifications in the N-direction

in the middle.) Again, MIN over the empty range is defined to yield a suitable value (i.e. $≥ 0$ )

R: $x = 0\min \left( {\operatorname{MIN}{mo} : 0 ≤ {mo} < M}\right)$

(M I N m 1: m 0 < m 1 ≤ M:

(M I N n 1: 0 ≤ n 1 < N; M S. m 0. m 1. (n 1 + 1))) *

M S. m 0. m 1. n 1 =

(\underline {{M I N}} n 0: 0 ≤ n 0 < n 1: (\underline {{\subseteq}} n: n 0 ≤ n < n 1: Q. m 0. m 1. n))

Q. m 0. m 1. n = (\underline {{S}} m: m 0 ≤ m < m 1: C. m. n)

*) Note that this line is equivalent to

(M I N n 1: 0 < n 1 ≤ N: M S. m 0. m 1. n 1))

Analogously to EWD897 we now derive two relations for MS

\begin{array}{l} M S. m 0. m 1. 0 = 0 (\mathrm {o r a n y v a l u e} ≥ 0) \tag {0} \ a n d f o r 0 ≤ n 1 < N \ M S. m 0. m 1. (n 1 + 1) \ = {\mathrm {d e f i n i t i o n o f} M S } \ (M I N n 0: 0 ≤ n 0 < n 1 + 1: (\sum n: n 0 ≤ n < n 1 + 1: Q. m 0. m 1. n)) \ = {\mathrm {i s o l a t i o n o f l a s t t e r m o f s u m m a t i o n} } \ (M I N n 0: 0 ≤ n 0 < n 1 + 1 \ (S n: n 0 ≤ n < n 1: Q. m 0. m 1. n) + Q. m 0. m 1. n 1) \ = {Q. m 0. m 1. n 1 \mathrm {d o e s n o t d e p e n d o n n 0 , a n d a d d i t i o n} \mathrm {t h e n d i s t r i b u t e s o v e r m i n i m i z a t i o n o v e r n o n - e m p l y r a n g e} } \ \end{array}

\begin{array}{l} = \left(\underset {\mathrm {Q . m 0 . m 1 . n 1}} {\mathrm {M I N}} n 0: 0 ≤ n 0 < n 1 + 1: (\underset {\mathrm {Q . m 0 . m 1 . n 1}} {\mathrm {S n}}: n 0 ≤ n < n 1: Q. m 0. m 1. n)\right) + \ = {\mathrm {i s o l a t i o n o f l a s t t e r m o f m i n i m i z a t i o n}; \mathrm {f o r} n 0 = n 1, \mathrm {t h e s u m m a t i o n y i e l d s 0} } \ \begin{array}{l} \left(\underline {{M I N}} n 0: 0 ≤ n 0 < n 1: (\underline {{S}} n: n 0 ≤ n < n 1: Q, m 0, m 1, n)\right) \underline {{m i n}} 0) + \ Q, m 0, m 1, n 1 \end{array} \ = {\mathrm {d e f i n i t i o n o f} M S } \ (M S. m 0. m 1. n 1 \underline {{m i n}} 0) + Q. m 0. m 1. n 1 \ \end{array}

For $Q$ we derive directly from its definition

\begin{array}{l} Q. m 0. m 0. n 1 = 0 (2) \ Q. m 0. (m 1 + 1). n 1 = Q. m 0. m 1. n 1 + C. m 1. n 1 (3) \ \end{array}

Our rewritten $\mathcal{R}$ tells us that for any $m_0,m_1$ combination we have to find the minimum of MS.m0.m1.(n1+1) for all n1: 0≤n1<N, while (1) gives a recurrence relation for that sequence of values. The snag is that that recurrence relation contains the term Q.m0.m1.n1, which - see (3)- satisfies a recurrence relation over m1. In order to exploit these two "orthogonal" recurrence relations to the fullest, the program evaluates for each value of mo the M-mo recurrences (1) that correspond to the different m1-values in syn-chrony. To this end, a local array MSv(m1: mo<m1≤M) is introduced such that, whenever MSv.m1 is adjusted, its value changes from MS.m0.m1.n1 to MS.m0.m1.(n1+1). Further more a local scalar Qv is introduced that satisfies

${Qv} = Q.m {0}.{m1}.{n1}$ . The program is given below; it reveals why we have written line*) in $R$ the way we did: we want to use each MS-value as soon as it has been computed, i.e. equals MS.m0.m1.(n1+1).

$\left[\begin{array}{l l} m 0: \text {int}; x:=0; m 0:=0\end{array}\right.$

$\therefore \underline{do}$ m0≠M→

\begin{array}{l} | M S v (m: m 0 < m ≤ M) \mathrm {a r r a y} \mathrm {o f i n t} \ ; m 1, n 1: i n t \ ; m 1 := m 0; \underline {{d o}} m 1 ≠ M \rightarrow m 1 := m 1 + 1; M S v. m 1 := 0 \underline {{o d}} \ ; n 1 := 0 \left{\left(\underline {{A}} m 1: m 0 < m 1 ≤ M: M S v. m 1 = M S. m 0. m 1. n 1\right), s e e (0) \right} \ ; \underline {{d o}} n 1 ≠ N \rightarrow \ \left[ Q v: i n t \right]; Q v, m 1 := 0, m 0 {Q v = Q. m 0. m 1. n 1, s e e (2) } \ ; \underline {{d o}} m 1 ≠ M \rightarrow \ Q v, m 1 := Q v + C. m 1. n 1, m 1 + 1 \ {Q v = Q, m 0. m 1, n 1, s e e (3) } \ ; M S v. m 1 := (M S v. m 1 \underline {{m i n}} 0) + Q v \ {M S v. m 1 = M S. m 0. m 1. (n 1 + 1), \mathrm {s e e} (1) } \ ; x := x \min M S v. m 1 \ o d; n 1 := n 1 + 1 \ \mathfrak {H} \ o d; m 0 := m 0 + 1 \ \mathbb {1} \ \prod^ {o d} \ \end{array}

History and acknowledgements I had just discussed (the linear) minsegsum in my lectures when Jon Bentley's article [0] appeared, in which he mentioned in passing the two-dimensional generalization. Solutions

of time-complexity $M^2\cdot N$ were independently found by Jayadev Misra, Mohamed G. Gouda and me. (Gouda's solution generates in turn the M.(M-1)/2 sequences of length N, to which minsegsum is applied; his solution needs all the time a linear array of length N, but is somewhat simpler than mine. How much store Misra intended to use I don't know.)

The above presentation has been influenced - and hopefully improved - by my course's audience, with which I discussed an earlier version. I am grateful to Shmuel Katz for insisting on an early inclusion of some heuristics for not trying to incorporate a "fighter coupling" in the M-direction and for accepting an asymmetric solution. The three 2x3 examples have been constructed in response to his request.

My earlier version refrained from defining a mini- mum for an empty set, and the formal derivation was less smooth. Halfway this note I got in panic: I failed to see how my derivation could ever yield the program I had derived earlier. The experience was instructive: I just went on and ....derived a program different from my earlier one! It so happens that replacing

M s v. m 1 := (M s v. m 1 \min 0) + Q v

by

M s v. m 1 := (M s v. m 1 + Q v) \min 0

changes the program into my earlier version. (For the earlier version to be correct, it is essential that the elements of Msv are initialized at 0.) There seems to be little point in comparing the relative merits of the two programs. The important lesson is that the formal derivation not only leads to new programs, but may even lead to programs one did not intend to derive! And this experience seems the most effective rebuttal of an opinion voiced by J.J. Seidel -a former colleague of mine- many years ago. I told him about formal program deriva- tion when that was still very new; he reacted with "But, sure, you'll never formally derive a program that you have not found already otherwise." At the time, that reaction struck me as an under- estimation of the power of formal techniques (an underestimation which was perhaps typical for the mathematicians of his generation).

Completed on 2 Dec. 1984

prof. dr. Edsger W. Dgkstra Department of Computer Sciences The University of Texas at Austin AUSTIN, TX 78712 - 1188 United States of America