Scribd
Upload
5 views1 page

Decision Trees and Backtracking Algorithms

The document outlines various algorithmic concepts and problems, including decision trees for sorting, backtracking for subset sum and N-queens problems, and branch-and-bound for knapsack problems. It also defines key computational complexity classes such as P, NP, and NP-complete, and differentiates between backtracking and branch-and-bound methods. Additionally, it provides a general algorithm for backtracking and discusses approximation algorithms for the knapsack problem.

Uploaded by

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

Decision Trees and Backtracking Algorithms

The document outlines various algorithmic concepts and problems, including decision trees for sorting, backtracking for subset sum and N-queens problems, and branch-and-bound for knapsack problems. It also defines key computational complexity classes such as P, NP, and NP-complete, and differentiates between backtracking and branch-and-bound methods. Additionally, it provides a general algorithm for backtracking and discusses approximation algorithms for the knapsack problem.

Uploaded by

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

Module-5

1. With example explain how decision trees are used for sorting algorithms. (10M)
2. Apply backtracking to solve the following instance of the subset sum problem:
A = {1, 3, 4, 5} and d = 11. Construct state space tree. (06M)
3. Solve following instance of the knapsack problem by using the branch-and-bound
technique. Given knapsack capacity=10. (10M)

4. Define P, NP and NP complete problems. (06M)


5. Differentiate between Back tracking and Branch-and-Bound. (04M)
6. Explain Backtracking method. Illustrate N queens problem using backtracking to
solve 4-queens problem. (10M)
7. Solve the the given instances of the subset sum problem. Construct a state space tree.
S = {5, 10, 12, 13, 15, 18} and d=30. (08M)
8. Write the general algorithm for backtracking. (04M)
9. Explain with example approximation algorithm for Knapsack problem. (10M)
10. Write a short note on following terms:
i) P-problems
ii) NP-problems
iii) Nondeterministic algorithm
iv) NP-Complete Problems
v) N-queens problem
vi) Subset sum problem
vii) Optimization problem

You might also like