1. The well-known document processing program TeX uses an optimization procedure to decompose a paragraph into several lines so that when lines are left and right adjusted, the appearance of the paragraph will be the most attractive. Suppose that a paragraph consists of n words and that each word is assigned a sequence number. Let cij denote the attractiveness of a line if it begins with the word i and ends with the word j 1. The program uses formulas to compute each cij . (a) Given the values for cij , show how to formulate the problem of decomposing the paragraph into several lines of text in order to maximize the total attractiveness (of all lines) as a shortest (or a longest) path problem. Give formal definitions for the sets of nodes and arcs, costs, source and destinations. (b) Does the corresponding graph have an acyclic ordering? Why