Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Implementation

Program gif defines the method typeset which takes three arguments. The first, l, is an array of n integers that gives the lengths of the words in the sequence to be typeset. The second, D, specifies the desired paragraph width and the third, s, specifies the normal inter-word space.

   program33453
Program: Dynamic programming example--typesetting a paragraph.

The method first computes the lengths, tex2html_wrap_inline67811, of all possible subsequences (lines 6-12). This is done by using the dynamic programming paradigm to evaluate the recursive definition of tex2html_wrap_inline67811 given in Equation gif. The running time for this computation is clearly tex2html_wrap_inline58122.

The next step computes the one-line penalties tex2html_wrap_inline67837 as given by Equation gif (lines 13-21). This calculation is a straightforward one and its running time is also tex2html_wrap_inline58122.

Finally, the minimum total costs, tex2html_wrap_inline67629, of typesetting each subsequence are determined for all possible subsequences (lines 22-37). Again we make use of the dynamic programming paradigm to evaluate the recursive definition of tex2html_wrap_inline67629 given in Equation gif. The running time for this computation is tex2html_wrap_inline58434. As a result, the overall running time required to determine the best way to typeset a paragraph of n words is tex2html_wrap_inline58434.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.