Scribd
Upload
2 views1 page

Module-5 Question Bank

The document is a question bank for the subject 'Analysis and Design of Algorithms' for the 4th semester, covering various topics including P, NP, NP-Complete, and NP-Hard problems. It includes questions on backtracking, branch and bound techniques, and greedy algorithms, with specific problems to solve such as the knapsack problem and the N-Queens problem. Each question is associated with a course outcome (CO), difficulty level, and marks allocation.

Uploaded by

sushma.aids
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

Module-5 Question Bank

The document is a question bank for the subject 'Analysis and Design of Algorithms' for the 4th semester, covering various topics including P, NP, NP-Complete, and NP-Hard problems. It includes questions on backtracking, branch and bound techniques, and greedy algorithms, with specific problems to solve such as the knapsack problem and the N-Queens problem. Each question is associated with a course outcome (CO), difficulty level, and marks allocation.

Uploaded by

sushma.aids
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

Subject Name: Analysis and Design of Algorithms Subject Code:

BCS401 SEM: 4th DIV: A


Faculty: SUSHMA M

Module-5 Question Bank

SL# Question CO Level Marks


Explain the following with examples
i) P problem
1. ii) NP Problem CO5 L2 10
iii) NP- Complete problem
iv) NP – Hard Problems
2. What is backtracking? Apply backtracking to solve the below
instance of sum of subset problem S={5,10,12,13,15,18} d=30 CO5 L3 10
3. Illustrate N queen’s problem using backtracking to solve 4-
CO5 L2 10
Queens problem
4. Using Branch and Bound technique solve the below instance of
knapsack problem.
Item Weight Value
1 2 12
2 1 10 CO5 L3 10
3 3 20
4 2 5
Capacity=5
5. Solve the following instance of the knapsack problem by the
branch-and-bound algorithm. Construct state-space tree.
Item Weight Value
1 4 $40
2 7 $42 CO5 L3 10
3 5 $25
4 3 $12
The knapsack's capacity W is 10.
6. Differentiate between Branch and Bound technique and
Backtracking. Apply backtracking-to solve the following CO5 L3 10
instance of subset-sum problem S = {3, 5, 6, 7} and d=15.
Construct a state space tree
7. Explain greedy approximation algorithm to solve discrete
CO5 L2 10
knapsack problem.

Faculty Signature

You might also like