G. L.
Bajaj Institute of Technology and Management, Greater NoidaDepartment
of Computer Science & Engineering
Assignment-4 (Unit-4)
Subject: Design & Analysis of Algorithm Subject code: KCS-503
Faculty Name: Ms. Paramjeet Kaur Session: 2023-24 (ODD)
Section: All Submission Date: 18/12/23
Issue Date: 11/12/2023
1. Explain the efficiency analysis for backtracking. (KCS-503.3,K1)
2. Differentiate between backtracking and branch & bound technique. (KCS-503.3,K2)
3. Describe the Wars hall’s and Floyd’s algorithm to finding all pair shortest path, Also give the time
complexity of both algorithm. (KCS-503.3,K1)
4. Write short note on the following: i) Hamiltonian cycle ii) Graph Colouring (KCS-503.3,K1)
5. Apply all-pairs shortest Path problem for the digraph with the weight matrix given below:
A B C D
A 0 ∞ ∞ 3
B 2 0 ∞ ∞ (KCS-503.3,K3)
C ∞ 7 0 1
D 6 ∞ ∞ 0
6. Design a recursive solution to the Longest Common Subsequence (LCS) problem. Determine an LCS of
(22112121) and (211221121). (KCS-503.3,K3)
7. Consider the knapsack with the corresponding weights and values for the following items:
Wi = < 2, 5, 3, 4 > Vi = < 3, 6, 5, 7 > Capacity = 10. (KCS-503.3,K3)
Apply the 0/1 knapsack problem using Dynamic Approach.
8. Given a set S = < 2, 5, 7, 9 > and X = 11. We have to find subset sum using Backtracking approach.
(KCS-503.3,K2)
9. Prove that if the weights on the edge of the connected undirected graph are distinct then there is a
unique Minimum Spanning Tree. Give an example in this regard. Also discuss Prim’s Minimum
Spanning Tree Algorithm in detail. (KCS-503.3,K4)
10. Give solution for 4 queen and 8 Queen problem. (KCS-503.3,K2)
11. What is Travelling Salesman Problem? Find the Solution of following Travelling Salesman Problem using
Branch and Bound Method. ȸ 20 30 10 11
15 ȸ 16 4 2
3 5 ȸ 2 4
Cost Matrix = 19 6 18 ȸ 3
16 4 7 16 ȸ
(KCS-503.3,K2)
12. Given a weighted directed graph G = (V, E) with Source “1” and weight function W:E → R, then write an
algorithm to solve a Single Source Shortest path problem whose complexity is O(VE). Apply the same on the
following graph.
(KCS-503.3,K4)
G. L. Bajaj Institute of Technology and Management, Greater NoidaDepartment
of Computer Science & Engineering
Assignment-5 (Unit-5)
Subject: Design & Analysis of Algorithm Subject code: KCS-503
Faculty Name: Ms. Paramjeet Kaur Session: 2023-24 (ODD)
Section: All Submission Date: 20/12/23
Issue Date: 18/12/2023
1. Explain the efficiency analysis for backtracking. (KCS-503.2,K1)
2. Describe Define Fast Fourier Transformation (FFT). (KCS-503.2,K1)
3. Describe P,NP and NP-complete class problem . Write 3 NP- complete class problems.(KCS-503.2,K1)
4. Describe amortized analysis? What are different methods used for it. Explain one of them with suitable
example. (KCS-503.2,K1)
5. Explain string matching problem and describe any string matching algorithm with suitable example.
(KCS-503.4,K1)
6. What are the string matching problems? Consider working module q = 11, how many
Spurious hits does the Ravin-Karp matcher counter in the tent T = 3141592653589793
When looking for the pattern P = 26? (KCS-503.2,K2)
7. What are randomized algorithms? Explain with example. (KCS-503.2,K1)
8. Explain and write Knuth-Morris-Pratt algorithm for pattern matching and also
comment on its running. (KCS-503.2,K1)
9. Show the comparisons made by Naïve string matcher for the pattern P={10001}in
the text T={0000100010010} . (KCS-503.2,K3)
