Assignment 1

1. Frame a tabulation listing the problems discussed in Unit I and II with the time complexity of each problem. CO1 & CO2 2. Multiply these numbers 981*1234 using Divide and conquer Concept and analyze its efficiency CO2 3. A graphic designer is working on a project that involves manipulating large images. The designer needs to perform matrix multiplications to apply transformations to the images. If the matrices are 1024x1024, and the standard matrix multiplication algorithm takes O(n^3) time, how much faster would Strassen's algorithm be? CO2 4. A thief has a knapsack that can hold a maximum weight of 8 kg. The thief wants to steal the following items: Item Weight Value Laptop 3 1000 Jewelry 2 800 Camera 1 400 Cash 2 600 Using dynamic programming, determine the optimal subset of items to include in the knapsack to maximize the total value while not exceeding the weight capacity. CO3 5. Using Warshall’s Algorithm construct the Transitive Closure of the directed graph shown below CO3