DAA CSE III-II MID-II Subjective

Subject Code: 21CS602PC MI21 H.T.No.
W 9
MALLA REDDY INSTITUTE OF ENGINEERING & TECHNOLOGY: SECUNDERABAD
III–B. TECH–II–Semester, II-MID Examinations (Regular) –Jul/Aug- 2024
Subject Name: DESIGN AND ANALYSIS OF ALGORITHMS
Branch: CSE Date: 31-07-2024 FN/AN
[Time: 90min] Session: FN [Max. Marks: 15M]
Note: Answer any Three questions from the following each question carries 5 Marks SET-1
Q CO B.T Marks
No
1. a) Solve the solution for 0/1 knapsack problem using dynamic 1 L2 3
programming: (p1,p2,p3, p4) = (2, 3, 1, 4), (w1, w2, w3, w4) = (3, 4, 6,
5), M=8,n=4.
1. b) State the principle of optimality in dynamic programming. How to apply 1 L2 2
this to the shortest path problem?
2. a) State the Job – Sequencing with deadlines problem. Find an optimal 2 L3 3

sequence to the n = 5 Jobs where profits (P1, P2, P3, P4, P5) = (20, 15,
10, 5, 1) and deadlines (d1, d2, d3, d4, d5) =(2, 2, 1, 3, 3).
2. b) Explain about single source shortest path problem in Greedy method. 1 L3 2
3. a) Explain the FIFO BB 0/1 Knapsack problem procedure with the 2 L4 3

knapsack instance for n=4, m=15 (p1, p2, p3, p4) = (10,10,12,18),
(w1, w2,w3,w4) =(2, 4, 6, 9). Draw the portion of the state space tree and
find optimal solution.
3. b) Explain NP hard and NP Complete with an example. 2 L4 2
4. Explain Travelling sales person problem LCBB procedure with the 2 L2 5

following instance and draw the portion of the state space tree and find
an optimal tour. ∞ 20 30 10 11
15 ∞ 16 4 2
3 5 ∞ 2 4
19 6 18 ∞ 3
16 4 7 16 ∞
5. Find the optimal solution for the knapsack problem by using Greedy 2 L3 5
method for all n=7, m=15 , (p1,p2,p3,p4,p5,p6,p7) = (10,5,15,7,6,18,3)
and (w1,w2,w3,w4,w5,w6,w7)=(2,3,5,7,1,4,1).
Subject Code: 21CS602PC MI21 H.T.No. W 9
[Time: 90 min] Session: FN [Max. Marks: 15M]
Note: Answer any Two questions from the following each question carries 5 Marks SET-2
Q.N CO B.T Marks
o
1. Construct a system with multiple devices connected parallel in three 1 L4 5
stages. The costs of the devices are 30, 15 and 20 respectively. The cost
of the system is to be no more than 105. The reliability of each device
type is 0.9, 0.8 and 0.5 respectively.
2. Explain Travelling sales person problem LCBB procedure with the 2 L2 5
following instance and draw the portion of the state space tree and find
an optimal tour.
∞ 20 30 10 11
15 ∞ 16 4 2
3 5 ∞ 2 4
19 6 18 ∞ 3
16 4 7 16 ∞
3. Explain the problem of job sequencing with deadlines by taking an 2 L3 5

example. Write the algorithm to solve the problem using the Greedy
Method. Show how the algorithm solves the following job sequencing
with deadlines problem. n = 4, (p1, p2, p3, p4) = (100, 10, 15, 27) and
(d1, d2, d3, d4) = (2, 1, 2, 1)
4. a) Describe LC branch and bound solution of 0/1 Knapsack problem in 1 L2 2.5
detail.
4. b) Explain FIFO branch and bound. 2 L3 2.5
5. Compute a minimum cost spanning tree for the graph shown below using 2 L2 5
a) Prim’s algorithm and b) Kruskal’s algorithm.
Subject Code: 21CS602PC MI21 H.T.No. W 9
[Time: 90min] Session: FN [Max. Marks: 15M]
Note: Answer any Three questions from the following each question carries 5 Marks SET-3
Q.N CO B.T Marks
o
1. Construct a system with multiple devices connected parallel in three 2 L2 5
stages. The costs of the devices are 25, 10 and 15 respectively. The cost
of the system is to be no more than 100. The reliability of each device
type is 0.8, 0.7 and 0.4 respectively.
2. a) Write about single source shortest path problem. 1 L1 2
2. b) What is Minimum cost spanning tree? Explain an algorithm for 2 L3 3

generating minimum cost spanning tree and list some applications of it.
3. a) What is the relation between NP-hard and NP-complete? 2 L3 3
3. b) Distinguish between deterministic and non-deterministic algorithm 1 L3 2
4. Draw the portion of the state space tree generated by LCBB for the 2 L3 5
knapsack instance: n=5,(p1,p2,p3,p4,p5)=(10,15,6,8,4),
(w1,w2,w3,w4,w5)=(4,6,3,4,2), and m=12.
5. Generate FIFO branch and bound solution for the given knapsack 2 L2 5
problem. m = 15, n = 3. (P1 P2 P3) = ( 10, 6, 8 ) (w1 w2 w3) = ( 10, 12,
3)

DAA CSE III-II MID-II Subjective

Uploaded by

Copyright:

Available Formats

DAA CSE III-II MID-II Subjective

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DAA CSE III-II MID-II Subjective

Uploaded by

Copyright:

Available Formats

Subject Code: 21CS602PC MI21 H.T.No.

[Time: 90min] Session: FN [Max. Marks: 15M]

2. a) State the Job – Sequencing with deadlines problem. Find an optimal 2 L3 3

3. a) Explain the FIFO BB 0/1 Knapsack problem procedure with the 2 L4 3

4. Explain Travelling sales person problem LCBB procedure with the 2 L2 5

[Time: 90 min] Session: FN [Max. Marks: 15M]

3. Explain the problem of job sequencing with deadlines by taking an 2 L3 5

4. b) Explain FIFO branch and bound. 2 L3 2.5

[Time: 90min] Session: FN [Max. Marks: 15M]

2. b) What is Minimum cost spanning tree? Explain an algorithm for 2 L3 3

3. a) What is the relation between NP-hard and NP-complete? 2 L3 3

3. b) Distinguish between deterministic and non-deterministic algorithm 1 L3 2

You might also like