Reference no: EM133550353

Question 1. Given an ordered sequence of numbers s = {s1,...,sn}, the max-sum problem is to find a contiguous subsequence of s with the greatest sum, that is, a subsequence {si...sj} that maximizes j j max{ E Sk : 1≤i≤n,1≤j ≤n}. k=1 For example, a subsequence of {2,-5,4,1,-2,3} with the greatest sum is {4,1,-2,3}, which has sum 6. (a) Give an efficient algorithm for max-sum that runs in time O(nlogn). (b) Improve your algorithm so that it runs in time Θ(n). 2. Consider the problem of word-wrapping a paragraph of text. A paragraph is an ordered list of n words, where word wi is i letters long. You want to divide the paragraph into a sequence of lines, each containing at most L letters. (No word is more than L letters long.) Suppose a line contains words wi...wj. The total length W(i,j) of this line is defined by j W(i,j) = j -i+ k=i k . This length accounts for a single space between successive pair of words on the line. The slop S(i,j) of this line is defined to be L-W(i,j), the total number of unused spaces at the end of the line. Note that in any feasible solution, the slop of each line must be non-negative. Just to make things concrete, consider the example paragraph "Now is the time for all good men.", and suppose L = 10. One feasible solution is Now is the time for all good men. This solution has four lines of lengths 10, 8, 8, and 4; the corresponding slops are 0, 2, 2, and 6. Your goal is to find a division of the input paragraph into lines that minimizes the sum, over all lines except the last, of the squared slop of each line. (We omit the last line because it can in general be much shorter than the others.) For example, the total cost of the above solution is 02 +22 +22 = 8. Give a polynomial-time algorithm for this problem.