algorithm design techniques this gives an ( algorithm to multiply -bit numbers compare this method to the solution in the text show how to multiply two numbers by solving five problems that are roughly one-third of the original size  generalize this problem to obtain an ( algorithm for any constant is the algorithm in part (bbetter than ( log ) why is it important that strassen' algorithm does not use commutativity in the multiplication of matrices two matrices can be multiplied using multiplications show how this can be used to improve the bound given by strassen' algorithm what is the optimal way to compute where the dimensions of the matrices area show that none of the following greedy algorithms for chained matrix multiplication work at each step compute the cheapest multiplication compute the most expensive multiplication compute the multiplication between the two matrices mi and mi+ such that the number of columns in mi is minimized (breaking ties by one of the rules abovewrite program to compute the best ordering of matrix multiplication include the routine to print out the actual ordering show the optimal binary search tree for the following wordswhere the frequency of occurrence is in parenthesesa ( )and ( ) ( )it ( )or ( extend the optimal binary search tree algorithm to allow for unsuccessful searches in this caseqj for < nis the probability that search is performed for any word satisfying wj wj+ is the probability of performing search for and qn is the probability of performing search  for wn notice that = pi = qj suppose ci, and that otherwise cij wij min (cik- ckj < <= suppose that satisfies the quadrangle inequalitynamelyfor all < < <jwij wij<wij wijsuppose furtherthat is monotoneif <iand <jthen wij <wija prove that satisfies the quadrangle inequality let rij be the largest that achieves the minimum cik- ckj (that isin case of tieschoose the largest prove that rij <rij+ <ri+ +