G. L.
Bajaj Institute of Technology and Management, Greater Noida
Department of Computer Science & Engineering
Assignment-3 (Unit-3)
Subject: Design & Analysis of Algorithm Subject code: KCS-503
Faculty Name: Ms. Paramjeet Kaur Session: 2023-24 (ODD)
Section: All Submission Date: 11/12/23
1. Write short note on convex hull with example. (KCS-503.5,K6)
2. Write steps are used in Dynamic Programming Approach? When and how it is applicable?
(KCS-503.3,K6)
3. Discuss the matrix-chain multiplication with respect Dynamic programming approach. (KCS-503.3,K2)
4. Explain the Floyd-Warshall algorithm with example. Which design strategy is used by this algorithm?
(KCS-503.5,K2)
5. Discuss the dynamic programming solution to longest common subsequence(LCS) problem. Write an
algorithm to compute an LCS of two given string. (KCS-503.3,K2)
6. Find Consider the five items along with their respective weights and values:
I = {I1, I2, I3, I4, I5}
W = {5, 10, 20, 30, 40}
V = {30, 20, 100, 90, 160}
The knapsack has capacity W = 60, find the solution of the Knapsack problem using Greedy
Criterion. (KCS-503.5,K1)
7. Show all the steps of Strassen’s Matrix Multiplication Algorithm to multiply the following matrices.
A=[2 3 , B=[1 3
4 5] 4 2] (KCS-503.5,K2)
8. Solve the following Activity Selection Problem using Greedy Approach.
S = <A1,A2,A3,A4,A5,A6,A7,A8,A9,A10>
Si = <1,3,0,5,3,5,6,8,8,12> Fi = < 4,5,6,7,8,9,10,11,12,14 > (KCS-503.5,K3)
9. Describe minimum cost spanning tree. Write Prim’s algorithm to generate MST . (KCS-503.4,K1)
10. Differentiate between Dijkstra’s and bellman ford algorithms with example.
(KCS-503.4, K2)
