Shanti Vardhak Education Society’s
Dept. of CSE / CSE(DS)
Class : 4th Semester 3rd IA Test Max. Marks :25
Sub : ADA (BCS401) 01-08-2024 Max. Time : 1:00 Hr.
Note: Answer any Two full question.
Module - 4
Q. 1] A) Solve the following instance of knapsack problem using dynamic 6.0
programming. Knapsack capacity is 5
Items Weights Value
1 2 $12
2 1 $10
3 3 $20
4 2 $15
B) Find the shortest distance and shortest path from vertex F to all vertices. 6.5
OR
Q. 2] A) Apply Prim’s & Kruskal’s Algorithm for the following graph 6.0
B) Construct a Huffman code for the following data: 6.5
Character A B C D -
Probability 0.4 0.1 0.2 0.15 0.15
Encode the text ABACABAD and decode 100010111001010
Module - 5
Q. 3] A) What backtracking? Drew the state space tree for solving the 4 queen’s 6.0
problem by back tracking method.
B) Construct the state-space tree for the sum of subset problem for the given 6.5
data. W={5, 10, 12, 13, 15, 18} and M=30
OR
Q. 4] A) Explain the classes of P, NP, and NP complete. 6.0
B) Apply Branch-and-bound technique for knapsack problem by taking 6.5
following value n=4, M=10
(P1, P2, P3, P4)=(40, 42, 25, 12) and (W1, W2, W3, W4)= (4, 7, 5, 3)
Shanti Vardhak Education Society’s
Dept. of CSE / CSE(DS)
Class : 4th Semester 3rd IA Test Max. Marks :25
Sub : ADA (BCS401) 01-08-2024 Max. Time : 1:00 Hr.
Note: Answer any Two full question.
Module - 4
Q. 1] A) Solve the following instance of knapsack problem using dynamic 6.0
programming. Knapsack capacity is 5
Items Weights Value
1 2 $12
2 1 $10
3 3 $20
4 2 $15
B) Solve the following single source shortest path’s problem with vertex a as 6.5
the source.
OR
Q. 2] A) Apply Prim’s & Kruskal’s Algorithm to find MST for the following graph 6.0
B) Construct a Huffman tree and resulting code word for the following? 6.5
Character A B C D -
Probability 0.35 0.1 0.2 0.2 0.15
Encode the word DAD and ADD
Module - 5
Q. 3] A) What backtracking? Drew the state space tree for solving the 4 queen’s 6.0
problem by back tracking method.
B) Draw the state space tree of the backtracking algorithm applied to the 6.5
instance S={11, 13, 24, 7} and d=31 of the subset sum problem.
OR
Q. 4] A) Explain the classes of P, NP, and NP complete. 6.0
B) Apply Branch-and-bound technique for knapsack problem by taking 6.5
following value n=4, M=10
(P1, P2, P3, P4)=(40, 42, 25, 12) and (W1, W2, W3, W4)= (4, 7, 5, 3)