Please help with exercise 11.10

Exercise 11.9. Let x and y be strings of symbols from some alphabet set of length m and n respectively (m need not be equal ton. Consider the oper- ations of deleting a symbol from r, inserting a symbol into x and replacing a symbol in z by another symbol (belonging to the alphabet set). Design an efficient algorithm using dynamic programming (in particular give the recursive formulation) to find the minimum number of such operations needed to transform z into y Exercise 11.10. Suppose you want to dial a telephone number consisting ofn digits on a standard 12-button telephone keypad, using the index fin gers of both hands. Assuming both fingers start over the 1 button, devise an O(n) tme algorithm using dynamic programming (in particular, give the recursive formulation) which determines which finger to use for each of the n digits so as to minimize the sum of the total distance traveled by both fin gers. Assume that the distance between two buttons i and j is given by the 11.4. EXERCISES function dist(i.j). You should first give the recursive formulation, clearly explaining what the subproblems are. Then devise two efficient algorithms that implements your recursive formulation- a recursive algorithm (us ing top-down, lookup strategy) and an iterative DP bottom-up strategy). Analyze the running time ofyour algorithms. Exercise 11.11. Consider the 0/1 Knapsack problem with two knapsacks having capacities ml and m2 respectively. We have n iterns x 1An. ltern r has an associated weightw and profitp. The goal is to fill as many items as possible in the two knapsacks so that we maximize the total profit. An item can be chosen to be put in either of the two knapsacks (if possible) or not chosen at all. Assume that weights, profits, mi, and m2 are all positive integers. (i) Show that the optimal substructure property holds for the problem. (ii) Let f,(yi, y2) be the optimal solution for the subproblem restricted to the first i items n, such that the two knapsacks have capacities yl and gp respectively. Give a recursive formulation for computing f,(i,y2) (iii) Give the pseudo-code of the resulting algorithm. You can give either a DP algorithm or a memoized algorithm. Analyze the running time of your algorithm. iu) Descrihe hou to change the algorithm so that it also generates the