1. Write brute force, greedy, dynamic algorithm and branch and bound algorithm for 0/1 knapsack problem. Find an optimal solution to the knapsack instance n=7, m=15,(p1,p2,.....p7)=(10,5,15,7,6,18,3) and (w1,w2,.....w7)=(2,3,5,7,1,4,1) using each of these approaches. Explain the time and space complexity of each approaches.

2. Given a chain of 4 matrices A1, A2, A3 and A4 with dimensions 5*4, 4*6, 6*2, and 2*7, respectively. Using Dynamic programming find the minimum number of scalar multiplications needed and also write the optimal multiplication order.