08-09-2016, 02:16 PM
[attachment=70749]
Define the knapsack problem and provide greedy solution for the problem instance
Analyze the quick sort algorithm for the given elements using Divide and Conquer technique
45, 32, 1, 65, 8, 33, 67, 56, 4, 77, 38
Define Algorithm and specify the criteria.
Compute time complexity for matrix multiplication
Explain Set operations
Provide tight bounds on T(n) for each of the following recurrences. Assume that T(n) is constant for sufficiently small n.
(a) T(n) = 7T(n/3) + n^2
(b) T(n) = 4T(n/2) + n^2
© T(n) = T(n − 2) + 2 log n
(d)) T(n) = T(n/2) + T(n/4) + T(n/8) + n
Implement the Merge sort algorithm to sort the given array of elements in non-decreasing order using Divide and Conquer Technique.
134, 435, 235, 812, 381, 527, 912, 43, 278,444
Using Greedy technique find an optimal solution to the Knapsack instance n=9, m=28, (p1,p2,…….p9) = (10,12,15,10,9,11,10,18, 13) and (w1,w2,…..w9) = (2,4,6,3,10,4,5,2,8).
Explain in brief Probabilistic Analysis and Amortized Analysis
Compute a minimum cost spanning tree for the given graph using
. a) Prim’s algorithm b) Kruskal’s algorithm
Compare Prim’s Algorithm with Kruskal’s Algorithm and identify which one will generate the minimum cost spanning tree
11. Consider the digraph given below and obtain the shortest paths in nondecreasing order of their lengths from vertex 1 to all remaining vertices using greedy method
12. Consider a four city TSP for which the cost between the city pairs are as shown in the figure below. Using Dynamic Programming technique find the tour of the salesman so that the cost of travel is minimum
13. Identify the articulation points and draw the biconnected components for the graphs given below.
14. For the given undirected graph obtain
i) DFS Spanning tree
ii) BFS Spanning tree
15. Let W = {5,7,10,12,15,18,20} and m = 35. Find all possible subsets of W that sum to m using Backtracking technique. Draw the portion of the state space tree that is generated.
16. Draw the portion of the state space tree generated by LCBB for the following Knapsack instance
n=5, (p1,…p5) = (10,15,6,8,4), (w1,…w5)=(4,6,3,4,2) and m=12
17. Draw the portion of the state space tree generated by FIFOBB for the following Knapsack instance
n=5, (p1,…p5) = (w1,…w5)=(4, 4, 5, 8, 9)) and m=15
18. Consider the traveling salesperson instance defined by the cost matrix
20. Differentiate NP-HARD and NP-COMPLETE Problems
21. Explain NP-Hard Graph Problems with examples
22. Construct an optimal binary search tree for the given identifier set
(a1,a2,a3,a4) = (count, float, if, while) with p(1)=1/20, p(2) = 1/5, p(3) = 1/10, p(4)=1/20, q(0) = 1/5, q(1) = 1/10, q(2) = 1/5, q(3) = 1/20 and q(4) = 1/20. Compute w(i,j), r( i, j ) and c( i, j), 0 <=I < j <=4.
23. Find a minimum cost edit sequence that transforms the string X to Y. Draw the cost table for the given example and the cost of insertion is Rs 2/- , cost of deletion is Rs 3/- and cost of change is Rs 3/-.
X = a, a, b, a, a, b, a, b, a, a
Y = b, a, b, a, a, b a, b.
24. Develop an algorithm to generate n Fibonacci numbers. Analyze the time complexity of the algorithm.
25. Provide the greedy solution for Job Sequencing with deadlines when n=7, (p1,p2,..p7) = (3, 5, 20, 18, 1, 6, 30) and (d1, d2, …d7) = (1, 3, 4, 3, 2, 1, 2).
26. Develop an algorithm to find the maximum and minimum item in a given set of n elements using Divide and Conquer Technique. Draw the Tree showing the recursive calls and analyze the time complexity for the given list of numbers
12, 45, 8, 56, 32, 90, 54, 88, 64, 27
27. Find a minimum cost path for the multistage graph given below using forward approach and backward approach
28. . Find the Shortest path form node 1 to every other node in the graph given below using Bellman and Ford algorithm.
29. Compare Greedy method and Dynamic Programming .
Solution : Greedy and Dynamic Programming are methods for solving optimization problems.
• Greedy algorithms are usually more efficient than DP solutions.
• However, often you need to use dynamic programming since the optimal solution cannot be guaranteed by a greedy algorithm.
• DP provides efficient solutions for some problems for which a brute force approach would be very slow.
• To use Dynamic Programming we need only show that the principle of optimality applies to the problem.
• Dynamic Programming is said to focus on the Principle of Optimality, "An optimal solution to any instance of an optimization problem is composed of optimal solutions to its sub instances".
• The greedy technique focuses on expanding partially constructed solutions until you arrive at a solution for a complete problem. It is then said, it must be "the best local choice among all feasible choices available on that step.
Define the knapsack problem and provide greedy solution for the problem instance
Analyze the quick sort algorithm for the given elements using Divide and Conquer technique
45, 32, 1, 65, 8, 33, 67, 56, 4, 77, 38
Define Algorithm and specify the criteria.
Compute time complexity for matrix multiplication
Explain Set operations
Provide tight bounds on T(n) for each of the following recurrences. Assume that T(n) is constant for sufficiently small n.
(a) T(n) = 7T(n/3) + n^2
(b) T(n) = 4T(n/2) + n^2
© T(n) = T(n − 2) + 2 log n
(d)) T(n) = T(n/2) + T(n/4) + T(n/8) + n
Implement the Merge sort algorithm to sort the given array of elements in non-decreasing order using Divide and Conquer Technique.
134, 435, 235, 812, 381, 527, 912, 43, 278,444
Using Greedy technique find an optimal solution to the Knapsack instance n=9, m=28, (p1,p2,…….p9) = (10,12,15,10,9,11,10,18, 13) and (w1,w2,…..w9) = (2,4,6,3,10,4,5,2,8).
Explain in brief Probabilistic Analysis and Amortized Analysis
Compute a minimum cost spanning tree for the given graph using
. a) Prim’s algorithm b) Kruskal’s algorithm
Compare Prim’s Algorithm with Kruskal’s Algorithm and identify which one will generate the minimum cost spanning tree
11. Consider the digraph given below and obtain the shortest paths in nondecreasing order of their lengths from vertex 1 to all remaining vertices using greedy method
12. Consider a four city TSP for which the cost between the city pairs are as shown in the figure below. Using Dynamic Programming technique find the tour of the salesman so that the cost of travel is minimum
13. Identify the articulation points and draw the biconnected components for the graphs given below.
14. For the given undirected graph obtain
i) DFS Spanning tree
ii) BFS Spanning tree
15. Let W = {5,7,10,12,15,18,20} and m = 35. Find all possible subsets of W that sum to m using Backtracking technique. Draw the portion of the state space tree that is generated.
16. Draw the portion of the state space tree generated by LCBB for the following Knapsack instance
n=5, (p1,…p5) = (10,15,6,8,4), (w1,…w5)=(4,6,3,4,2) and m=12
17. Draw the portion of the state space tree generated by FIFOBB for the following Knapsack instance
n=5, (p1,…p5) = (w1,…w5)=(4, 4, 5, 8, 9)) and m=15
18. Consider the traveling salesperson instance defined by the cost matrix
20. Differentiate NP-HARD and NP-COMPLETE Problems
21. Explain NP-Hard Graph Problems with examples
22. Construct an optimal binary search tree for the given identifier set
(a1,a2,a3,a4) = (count, float, if, while) with p(1)=1/20, p(2) = 1/5, p(3) = 1/10, p(4)=1/20, q(0) = 1/5, q(1) = 1/10, q(2) = 1/5, q(3) = 1/20 and q(4) = 1/20. Compute w(i,j), r( i, j ) and c( i, j), 0 <=I < j <=4.
23. Find a minimum cost edit sequence that transforms the string X to Y. Draw the cost table for the given example and the cost of insertion is Rs 2/- , cost of deletion is Rs 3/- and cost of change is Rs 3/-.
X = a, a, b, a, a, b, a, b, a, a
Y = b, a, b, a, a, b a, b.
24. Develop an algorithm to generate n Fibonacci numbers. Analyze the time complexity of the algorithm.
25. Provide the greedy solution for Job Sequencing with deadlines when n=7, (p1,p2,..p7) = (3, 5, 20, 18, 1, 6, 30) and (d1, d2, …d7) = (1, 3, 4, 3, 2, 1, 2).
26. Develop an algorithm to find the maximum and minimum item in a given set of n elements using Divide and Conquer Technique. Draw the Tree showing the recursive calls and analyze the time complexity for the given list of numbers
12, 45, 8, 56, 32, 90, 54, 88, 64, 27
27. Find a minimum cost path for the multistage graph given below using forward approach and backward approach
28. . Find the Shortest path form node 1 to every other node in the graph given below using Bellman and Ford algorithm.
29. Compare Greedy method and Dynamic Programming .
Solution : Greedy and Dynamic Programming are methods for solving optimization problems.
• Greedy algorithms are usually more efficient than DP solutions.
• However, often you need to use dynamic programming since the optimal solution cannot be guaranteed by a greedy algorithm.
• DP provides efficient solutions for some problems for which a brute force approach would be very slow.
• To use Dynamic Programming we need only show that the principle of optimality applies to the problem.
• Dynamic Programming is said to focus on the Principle of Optimality, "An optimal solution to any instance of an optimization problem is composed of optimal solutions to its sub instances".
• The greedy technique focuses on expanding partially constructed solutions until you arrive at a solution for a complete problem. It is then said, it must be "the best local choice among all feasible choices available on that step.