algorithm design techniques consider the problem of right-justifying paragraph the paragraph contains sequence of words wn of length an which we wish to break into lines of length words are separated by blanks whose ideal length is (millimeters)but blanks can stretch or shrink as necessary (but must be > )so that line wi wi+ wj has length exactly howeverfor each blank bwe charge |bbugliness points the exception to this is the last linefor which we charge only if bb (in other wordswe charge only for shrinking)since the last line does not need to be justified thusif bi is the length of the blank between ai and ai+ then the ugliness of setting any line (but the lastwi wi+ wj for  - is = |bk ( )|bb|where bis the average size of blank on this line this is true of the last line only if bbotherwise the last line is not ugly at all give dynamic programming algorithm to find the least ugly setting of wn into lines of length (hintfor nn compute the best way to set wi wi+ wn give the time and space complexities for your algorithm (as function of the number of wordsnc consider the special case where we are using fixed-width fontand assume the optimal value of is (spacein this caseno shrinking of blanks is allowedsince the next smallest blank space would be give linear-time algorithm to generate the least ugly setting for this case the longest increasing subsequence problem is as followsgiven numbers an find the maximum value of such that ai ai aik and ik as an exampleif the input is the maximum increasing subsequence has length four ( among othersgive an ( algorithm to solve the longest increasing subsequence problem the longest common subsequence problem is as followsgiven two sequences am and bn find the lengthkof the longest sequence ck such that is subsequence (not necessarily contiguousof both and as an exampleif dynamic and programmingthen the longest common subsequence is , , and has length give an algorithm to solve the longest common subsequence problem your algorithm should run in (mntime the pattern-matching problem is as followsgiven stringsof textand patternpfind the first occurrence of in approximate pattern matching allows mismatches of three types( character can be in that is not in ( character can be in that is not in ( and can differ in position