PRINTED PAGES : 2
Paper ID: 17420 Roll No..............................
END-SEMESTER EXAMINATION, 2023-24
B. Tech. (SEMESTER : 05)
CSE 356 : DESIGN AND ANALYSIS OF ALGORITHM
Time: 3 Hrs. Max. Marks: 100
Note: 1. All questions are compulsory.
2. Assume missing data suitably, if any.
CO1: Analyze the asymptotic performance of algorithms.
CO2: Describe the dynamic-programming and Greedy paradigm and explain when an algorithmic
design situation calls for it.
CO3: Demonstrate a familiarity with major algorithms and data structures.
CO4: Apply important algorithmic design paradigms and methods of analysis.
CO5: Discuss NP-complete problems and develop algorithms to solve the problems.
CO6: Choose appropriate algorithm design techniques for solving problems.
COS Marks BTL
SECTION-A
All Questions are Compulsory: (10×4=40 Marks)
1. Define and visually describe the different asymptotic notations used to CO1 4 K1
calculate the running time complexity of an algorithm.
2. Explain the Master’s theorem. CO1 4 K2
3. Compare Greedy programming with Dynamic Programming CO2 4 K1
4. Explain working of Digkastra’s algorithm with an example if n = 6. CO2 4 K2
5. Explain taking an example, 1x1=5, 1y1=6, how longest common CO3 4 K2
subsequence works when string x is compared with y.
6. Build an algorithm for Floyyd warshal algorithm. CO3 4 K3
7. Explain insertion in Red Black Tree. CO4 4 K2
8. Apply Union on two disjoint sets. Explain taking an example. CO4 4 K3
9. Explain polynomial time reducibility. Give Examples. CO5 4 K2
10. Apply the left rotation in RB tree with example. CO5 4 K3
f
SECTION-B
All Questions are Compulsory: (3×6=18 Marks)
11. (a) Classify and Distinguish between 0/1 knapsack and fractional Knapsack CO3 6 K4
applying Dynamic and Greedy Programming respectively.
--- OR ---
(b) List and explain the characteristic properties associated with a problem
that can be solved using dynamic programming.
12. (a) Examine construction of Fibonacci Heaps with suitable example. CO4 6 K4
--- OR ---
1 12
(b) Examine Randomised algorithm with suitable example.
13. (a) Examine and Elaborate the principles of B-Trees construction and CO5 6 K4
deletion of elements taking suitable values of order t.
--- OR ---
(b) Examine and Elaborate Vertex Cover Problem.
SECTION-C
All Questions are Compulsory: (3×10=30 Marks)
14. (a) Discover the longest common subsequence using dynamic programming. CO3 10 K4/K5
X=ABBCT Y=ABDCAB.
--- OR ---
(b) Solve matrix chain multiplication using dynamic programming with
matrices A1,………A5 and P0 = 10, P1 : 2P2:1, P3 : 5, P4 : 5, P5:10.
15. (a) Inspect while inserting In R-B tree 7,9,10,11,8,12,18,3. Now delete in CO4 10 K4/K5
order:8, 11, 18. Visually show all steps.
--- OR ---
(b) Discuss the notion of NP Complete and NP Hard Problems with
examples. Let S be an NP-complete problem and Q and R be two other
problems not known to be in NP. Q is polynomial time reducible to S and
S is polynomial-time reducible to R. Classify P, Q, and R as either NP-
complete or NP-hard.
16. (a) Explain Travelling Salesman Problem (TSP). Explain the basic steps that CO5 10 K4/K5
are to be followed to solve TSP using branch and bound with an
example.
--- OR ---
(b) Survey the rules that all red black trees follow. Explain with the help of a
suitable example.
SECTION-D
Attempt the following Question: (1×12=12 Marks)
17. (a) Explain the following taking an example n – 21: CO6 12 K5/K6
(i) (Insertion), (ii) (Deletion of min) element in min binomial heap.
--- OR ---
(b) Explain String Matching Algorithm using a suitable example.
*******
2 22
