Consider the 0-1 knapsack problem for items 1,2,3,4,5, whose values are [4, 3, 6, 5, 7] and whose weights are [2, 2, 3, 4, 5]. Assume the knapsack capacity is 10. Apply the knapsack algorithm in the lecture notes to the problem by filling the array A[5, 10],

Question 1. (15 marks) a. (5 marks) Consider the 0-1 knapsack problem for items 1 whose values are 4,3, 6, 5, 7 and whose weights are 2,2, 3, 4, 5. Assume the knapsack capacity is 10. Apply the knapsack algorithm in the lecture notes to the problem by filling the array A5, 10], and apply the Print-Opt-Knapsack procedure to show which items are in your optimal solution. b. (5 marks) Matrices A, B, C, D, E have respective dimensions 1 x 5, 5 x 2, 2 x 6, 6 x 1, 1 x 4. What is the minimum number of scalar multiplications needed to compute A x Bx C x D x E? Give the parenthesization of matrices that yields this number. Show how you arrived at your answer c. (5 marks) se Stressen's algorithm to compute the following matrix product. Show your work, but for multiplications involving only 2 x 2 matrices you can just give the result. 8 2 31 3 2 44 81 7 4 5 5 1 1 6 3 2 3 5 5 2 2 6 3 7 3 6 3 1 5 4 1 4