Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Implementation

Program gif defines the function Typeset which takes three arguments. The first, l, is an array of n unsigned 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.

   program33913
Program: Dynamic Programming Example--Typesetting a Paragraph

The routine first computes the lengths, tex2html_wrap_inline69093, of all possible subsequences (lines 5-11). This is done by using the dynamic programming paradigm to evaluate the recursive definition of tex2html_wrap_inline69093 given in Equation gif. The running time for this computation is clearly tex2html_wrap_inline59179.

The next step computes the one-line penalties tex2html_wrap_inline69119 as given by Equation gif (lines 12-20). This calculation is a straightforward one and its running time is also tex2html_wrap_inline59179.

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


next up previous contents index

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