In this problem. we would like to break a sequence of words into a series of lin

Question

In this problem. we would like to break a sequence of words into a series of lines to form paragraph. Our objective is to ovoid extra spaces on any line. The order of words must be maintained as they are pieced on lines. Assume o sequence of n words of length wl, w2, w3.....wn and a line width of W. The constraint in this problem is that, if a line contains word I through word j, then wi+_+wj+(j-i)= W. Note that the term j-1 corresponds to the number of spoces required to separate the words. We define an objective as follow: The cost associated for each line is the number of extra spaces on the line: Give a greedy algorithm for this problem and analyze its time complexity.

Explanation / Answer

A greedy algorithm looks for a local optimum, instead of a global optimum Consider the following greedy algorithm: SpaceLeft := W for each Word in Text indexed i: if (wi + 1) > SpaceLeft insert line break before Word in Text SpaceLeft := W - wi else SpaceLeft := SpaceLeft - (wi + 1) Time Complexity = O(n) as each word is being processed exactly once.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.