6. The input to this problem consists of an ordered list of n words. The length...

Transcribed Image Text:

6. The input to this problem consists of an ordered list of n words. The length of the ith word is wi, that is the ith word takes up w; spaces. (For simplicity assume that there are no spaces between words.) The goal is to break this ordered list of words into lines; this is called a layout. Note that you cannot reorder the words. The length of a line is the sum of the lengths of the words on that line. The maximum line length is L. Assume that w; L for all i. No line may be longer than L, although it may be shorter. The penalty for having a line of length K < L is L - K. Consider the following greedy algorithm. For i = 1 to n Place the ith word on the current line if it fits else place the ith word on a new line (a) The overall penalty is defined to be the sum of the line penalties. The problem is to find a layout that minimizes the overall penalty. Prove of disprove that the above greedy algorithm correctly solves this problem. (b) The overall penalty is now defined to be the maximum of the line penalties. The problem is to find a layout that minimizes the overall penalty. Prove of disprove that the above greedy algorithm correctly solves this problem. 6. The input to this problem consists of an ordered list of n words. The length of the ith word is wi, that is the ith word takes up w; spaces. (For simplicity assume that there are no spaces between words.) The goal is to break this ordered list of words into lines; this is called a layout. Note that you cannot reorder the words. The length of a line is the sum of the lengths of the words on that line. The maximum line length is L. Assume that w; L for all i. No line may be longer than L, although it may be shorter. The penalty for having a line of length K < L is L - K. Consider the following greedy algorithm. For i = 1 to n Place the ith word on the current line if it fits else place the ith word on a new line (a) The overall penalty is defined to be the sum of the line penalties. The problem is to find a layout that minimizes the overall penalty. Prove of disprove that the above greedy algorithm correctly solves this problem. (b) The overall penalty is now defined to be the maximum of the line penalties. The problem is to find a layout that minimizes the overall penalty. Prove of disprove that the above greedy algorithm correctly solves this problem.