- define the edit distance between two strings and of length and mrespectivelyto be the number of edits that it takes to change into an edit consists of character insertiona character deletionor character replacement for examplethe strings "algorithmand "rhythmhave edit distance design an (nm)-time algorithm for computing the edit distance between and - let and be strings of length and mrespectively define bjkto be the length of the longest common substring of the suffix [ :nand the suffix [ :mdesign an (nm)-time algorithm for computing all the values of bjkfor and - anna has just won contest that allows her to take pieces of candy out of candy store for free anna is old enough to realize that some candy is expensivewhile other candy is relatively cheapcosting much less the jars of candy are numbered so that jar has pieces in itwith price of per piece design an ( )-time algorithm that allows anna to maximize the value of the pieces of candy she takes for her winnings show that your algorithm produces the maximum value for anna - let three integer arraysaband cbe giveneach of size given an arbitrary integer kdesign an ( log )-time algorithm to determine if there exist numbersa in ab in band in csuch that - give an ( )-time algorithm for the previous problem - given string of length and string of length mdescribe an ( )-time algorithm for finding the longest prefix of that is suffix of - give an efficient algorithm for deleting string from standard trie and analyze its running time - give an efficient algorithm for deleting string from compressed trie and analyze its running time - describe an algorithm for constructing the compact representation of suffix triegiven its noncompact representationand analyze its running time projects - use the lcs algorithm to compute the best sequence alignment between some dna stringswhich you can get online from genbank - write program that takes two character strings (which could befor examplerepresentations of dna strandsand computes their edit distanceshowing the corresponding pieces (see exercise -