- modify the simplified boyer-moore algorithm presented in this using ideas from the kmp algorithm so that it runs in ( mtime - design an efficient algorithm for the matrix chain multiplication problem that outputs fully parenthesized expression for how to multiply the matrices in the chain using the minimum number of operations - native australian named anatjari wishes to cross desert carrying only single water bottle he has map that marks all the watering holes along the way assuming he can walk miles on one bottle of waterdesign an efficient algorithm for determining where anatjari should refill his bottle in order to make as few stops as possible argue why your algorithm is correct - describe an efficient greedy algorithm for making change for specified value using minimum number of coinsassuming there are four denominations of coins (called quartersdimesnickelsand pennies)with values and respectively argue why your algorithm is correct - give an example set of denominations of coins so that greedy changemaking algorithm will not use the minimum number of coins - in the art gallery guarding problem we are given line that represents long hallway in an art gallery we are also given set { xn- of real numbers that specify the positions of paintings in this hallway suppose that single guard can protect all the paintings within distance at most of his or her position (on both sidesdesign an algorithm for finding placement of guards that uses the minimum number of guards to guard all the paintings with positions in - let be convex polygona triangulation of is an addition of diagonals connecting the vertices of so that each interior face is triangle the weight of triangulation is the sum of the lengths of the diagonals assuming that we can compute lengths and add and compare them in constant timegive an efficient algorithm for computing minimum-weight triangulation of - let be text string of length describe an ( )-time method for finding the longest prefix of that is substring of the reversal of - describe an efficient algorithm to find the longest palindrome that is suffix of string of length recall that palindrome is string that is equal to its reversal what is the running time of your methodc- given sequence ( xn- of numbersdescribe an ( )time algorithm for finding longest subsequence (xi xi xik- of numberssuch that xi + that ist is longest decreasing subsequence of - give an efficient algorithm for determining if pattern is subsequence (not substringof text what is the running time of your algorithm