Scribd
Upload
20 views

DAA Assignment-4 & 5

Uploaded by

naneet yadav
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
20 views

DAA Assignment-4 & 5

Uploaded by

naneet yadav
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

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)

You might also like