ANSWER THE Q3 !!!!!!!!

2. [10 marks] Suppose you are developing the prototype of a web browser. At some stage you need to design a way of breaking an English paragraph into lines to display it in the browser; naturally you would like to make the lines look good. Suppose that each line always displays a set of words, that is, we do not hyphenate words for line breaks To define this problem, we are given a list of n words, W-{wi, w2, .. ., wm^, repre- senting a paragraph, where ui is the i-th word in the paragraph. For each word wi, we are given its length l,. We also know the maximum number, m, of characters that can be displayed in each line of the browser. We know in advanced that w, m for each i Our goal is to break W into lines in a way that minimizes a total cost penalizing the wasted space. The cost of breaking a single line to display the words wi, wi+i,... ,wj has cost if this cost if nonnegative (to understand this function, think of (j - i) as the number of space characters needed to separate these words; then c(i, j) can be viewed as the cube of the wasted space of this line). If this cost is negative, then we set c(i,j) - +00 instead, to show that the words {uwi+1, , uy} do not fit in a single line Furthermore, if this cost is positive and = n, that is, this positive cost is for the last line used to display this paragraph, then we set c(i.j)-0. That is, we do not penalize the wasted space in the last line To calculate the total cost penalizing the wasted space, you simply sum up the above cost of each line used to display the paragraph Now, use dynamic programming to design an efficient algorithm to solve this problem optimally. In this question, you are only required to report the value of the minimum total cost 3. [10 marks For the problem in question 2, design an efficient algorithm to actually break the paragraph into lines optimally. The output of your algorithm should report which word appears as the last word in each line