Consider the problem of neatly printing a paragraph on a printer. The input text is a sequence of n words of lengths l1, l2, ..., ln, measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of M characters each. Our criterion of "neatness" is as follows. If a given line contains words i through j, where i ≤ j, and we leave exactly one space between words, the number of extra space characters at the end of the line is , which must be nonnegative so that the words fit on the line. We wish to minimize the sum, over all lines except the last, of the cubes of the numbers of extra space characters at the ends of lines. Give a dynamic-programming algorithm to print a paragraph of n words neatly on a printer. Analyze the running time and space requirements of your algorithm.
Answer to relevant QuestionsIn order to transform one source string of text x [1 ¬ m] to a target string y [1 ¬ n], we can perform various transformation operations. Our goal is, given x and y, to produce a series of transformations that change x to ...Given an m × n matrix T over some field (such as the reals), show that (S,ℓ) is a matroid, where S is the set of columns of T and A ¬ℓ if and only if the columns in A are linearly independent.A sequence of stack operations is performed on a stack whose size never exceeds k. After every k operations, a copy of the entire stack is made for backup purposes. Show that the cost of n stack operations, including copying ...Given a weighted, directed graph G = (V, E) with no negative-weight cycles, let m be the maximum over all pairs of vertices u, v ¬ V of the minimum number of edges in a shortest path from u to v. (Here, the shortest ...Repeat Exercise 5.6 but make the operator an update operator.
Post your question