Scribd
Upload
2 views1 page

DAA AssignmentII

This document is an assignment for the I/IV B.Tech. (Data Science) students at R.V.R. & J.C. College of Engineering, focusing on Design & Analysis of Algorithms. It includes questions on Multi Stage Graphs, 0/1 Knapsack problems, Hamiltonian Cycles, state space trees, and differentiating Backtracking with Branch & Bound. The assignment is structured to assess understanding of key concepts in algorithm design and analysis.

Uploaded by

rajeshnemalipuri1
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views1 page

DAA AssignmentII

This document is an assignment for the I/IV B.Tech. (Data Science) students at R.V.R. & J.C. College of Engineering, focusing on Design & Analysis of Algorithms. It includes questions on Multi Stage Graphs, 0/1 Knapsack problems, Hamiltonian Cycles, state space trees, and differentiating Backtracking with Branch & Bound. The assignment is structured to assess understanding of key concepts in algorithm design and analysis.

Uploaded by

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

R.V.R. & J.C.

COLLEGE OF ENGINEERING (AUTONOMOUS), CHOWDAVARAM


Department of Computer Science & Engineering (Data Science)
I/IV [Link]., (DS) ASSIGNMENT - II Time: 45 Mts.
2024-25 (IV Semester) [Link]: 12

CD225- Design & Analysis of Algorithms

1 Explain about Multi Stage Graph (Forward Approach) with an example. 6M CO3

Solve the following 0/1 Knapsack problem using Dynamic Programming 6M CO3
2
n=3, M=6, (P1, P2, P3) = ( 1, 2, 5), ( W1,W2,W3) = ( 2, 3, 4).

3 Explain about Hamiltonian Cycles with an example. 6M CO3

Construct the Portion of state space tree generate by Least Cost 0/1 6M CO4
4 Knapsack for the instance, n=4, ( P1, P2, P3, P4 )= ( 10, 10, 12, 18 ),
( W1, W2, W3, W4 ) = ( 2, 4, 6, 9 ) and M =15.

5 Differentiate Backtracking with Branch & Bound. 6M CO4

6 Explain about Cook’s Theorem and Node Covering Problem. 6M CO4

You might also like