Scribd
Upload
3 views1 page

Module - 5

The document outlines various concepts in algorithm analysis, including limitations of algorithmic power, decision trees, and classifications of problems such as P, NP, and NP-Complete. It also discusses techniques like backtracking, Branch and Bound, and approximation algorithms, along with specific problems like the N-Queens problem and Subset Sum. Additionally, it includes practical applications and examples for solving the 0/1 Knapsack problem and analyzing greedy algorithms.

Uploaded by

money2005qw
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
3 views1 page

Module - 5

The document outlines various concepts in algorithm analysis, including limitations of algorithmic power, decision trees, and classifications of problems such as P, NP, and NP-Complete. It also discusses techniques like backtracking, Branch and Bound, and approximation algorithms, along with specific problems like the N-Queens problem and Subset Sum. Additionally, it includes practical applications and examples for solving the 0/1 Knapsack problem and analyzing greedy algorithms.

Uploaded by

money2005qw
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. What are the limitations of algorithmic power.


2. decision tree in algorithm analysis?
3. Define class P , NP and NP-Complete problem? with an example.
4. Explain State , State space , State space tree
5. backtracking technique. two applications of backtracking.
6. N-Queens problem?
7. Subset Sum problem.
8. Describe Branch and Bound technique?
9. Define approximation algorithm. What is approximation ratio?
10. Analyze the decision tree model for selection sort: construct its decision tree and
prove it has at least n! leaves; hence deduce the n log n lower bound on comparisons
11. Subset Sum problem.
set , S={3,5,6,7}
target sum , M=12
12. Set, S={4,5,7} target sum, M=9
13. Solve the 0/1 Knapsack problem using the Branch and Bound method for the
following data:
Weights = {2, 3, 4, 5}
Profits = {3, 4, 5, 6}
Capacity = 5
14. Analyze the greedy approximation algorithm to solve the Knapsack problem with the
following data and compute the approximation ratio.
Weights = {10, 20, 30}
Profits = {60, 100, 120}
Capacity = 50
15.

You might also like