Given n and k with n 0 and k 0, we want to compute a new function f(n, k) using the following recurrence: Base Cases: f(n,0) = 3n and f(0, k) = 2k, for n, k 0 Recursive Case: f(n, k) = f(n 1, k 1) + f(n 1, k) + (n, k 1) (1) Give pseudo-code for a bottom-up dynamic programming algorithm to compute f(n, k) using the above recurrence. (2) Show the dynamic programming table your algorithm creates for (2, 4). Consider the optimization problem max 4u1+5u2+4u3+8u4+6u5 4u1+6u2+5u3+9u4+7u5 < 19 uj0, j=1,...,5. (a) Assume that all u; may take only values 0 or 1. Solve the problem by dynamic programming. Draw the graph of the equivalent longest path problem. (b) Assume that all u; may take nonnegative integer values. Solve the problem by dynamic programming. In both cases, use the backward version of dynamic programming, calculating the value functions VN(x), VN-1(x), ..., v(x) for all possible states x. 1. For a computational system to calculate, L= - Where x=-3,y=2, and == 0.3, do the given following problems: (Notice that a similar problem was given in your homework) (6 point) a) Draw the computational graph to calculate L. (1 point) b) Using the dynamic programming (i.e., using the "upstream gradient" and "local gradient"), obtain the 4 (2 point) c) Using the dynamic programming (i.e., using the "upstream gradient" and "local gradient"), obtain the (1 point) d) Using the dynamic programming (i.e., using the "upstream gradient" and "local (1 point) gradient"), obtain the JL Jz How dynamic programming is good compare to greedy technique. Also relate dynamic programming technique with divide and conquer approach. Suppose, we have 4 matrices: A: 30 x 1 B: 1x 40 C: 40 x 10 D: 10 x 25. Find the optimal number of multiplication using 10 dynamic programming. What do you mean spurious hit in Rabin Karp string matching algorithm? Construct the string-matching automaton for the pattern aabab and illustrate its operation on the text string aaababaabaababaab, Also find number of spurious hits? 000 10