Anna University Chennai - Important Questions of CS6402 Design and Analysis of Algorithms B.E/B.TECH DEGREE EXAMINATION NOV / DEC 2016
IV Semester / 04th Semester / Fourth Semester
Department of Computer Science Engineering CSE
CS6402 Design and Analysis of Algorithms
Nov Dec 2016 Important Questions
(Regulation 2013)
CS6402 Design and Analysis of Algorithms - All Important 16 Marks Questions
1. (i) Describe fundamentals of algorithmic problem solving. (10)
(ii) Describe the most important problem types are used to illustrate different algorithm design techniques and methods of algorithm analysis? (6)
2. Show the following equalities are correct.
i. 5n^2 – 6n= Ө (n^2) (4)
ii. n!= O(n^n) (4)
iii. n^3 + 106 ^ = Ө (n^3) (4)
iv. 2n^2 x 2^n + nlogn = Ө (n^2 x 2^n)
3. (i) Prove that for any two functions f (n) and g(n) , we have f (n) = θ (g(n)) if and only (n) = O (g(n)) and f (n) = Ω(g(n)) . (8)
(ii) Classify the various asymptotic notations. (8)
4. If you have to solve the searching problem for a list of n numbers, how can you take advantage of the fact that the list is known to be sorted?
Give separate answer for
(i) Lists represented as arrays.
(ii) Lists represented as linked lists.
Compare the time complexities involved in the analysis of both the algorithms.
5. Explain the recursive algorithm for computing Fibonacci numbers and analyze the same.
6. (i) Explain the Closest pair and convex hull problem in detail. (10)
(ii) Explain the concepts of Brute force string matching. (6)
7. (i) Write down the algorithm to construct a convex hull based on divide and conquer strategy. (8)
(ii) Find the optimal solution to the fractional knapsack problem with the given data: (8)
ITEM WEIGHT BENEFIT
A 2 60
B 3 75
C 4 90
8. (i) Solve the following using Brute – Force algorithm: (10)
Find whether the given string follow the specified pattern and return 0 or 1 accordingly.
Examples:
(1) Pattern: “abba” , input: “redblueredblue” should return 1
(2) Pattern: “aaaa” , input: “asdasdasdasd” should return 1
(3) Pattern: “aabb” , input: “xyzabcxyzabc” should return 0
(ii) Explain the convex hull problem and the solution involved behind it. (6)
9. (i) Write an algorithm to perform binary search on a sorted list of elements. (8)
(ii) Analyze the binary search algorithm for the best, average and worst case (8)
10. Design the knapsack problem with suitable example.
11. Explain Warshall’s and Floyd’s algorithm with suitable examples.
12. (i) Write and analyze the Prim’s Algorithm. (6)
(ii) Consider the following weighted graph. (10)
Give the list of edges in the MST in the order that Prim’s Algorithm inserts them. Start Prim’s Algorithm from vertex A.
19. (i) Briefly describe on the stable marriage problem (6)
(ii) How do you compute maximum flow for the following graph using Ford Fulkerson method? (10)
23. (i) Show that the Hamiltonian path problem reduces to the Hamiltonian circuit Problem and vice versa. (10)
(ii) What is an Approximation Algorithm? Give Example. (6)
24. (i) The knight is placed on the first block of the empty board and, moving according to the rules of chess, must visit each square exactly once. Solve the above problem using backtracking procedure. (10)
(ii) Implement an algorithm for Knapsack problem using NP-Hard approach. (6)
25. Using branch and bound, describe how to find the optimal solution to a knapsack problem for the knapsack instance n = 8, m = 110, (p1, p2. ... p7) = (11, 21, 31, 33, 43, 53, 55, 65) and (w1, w2,...,w7) = (1, 11, 21, 33, 43, 53, 55, 56).
IUQP wishes you to get success in the examination of CS6402 Design and Analysis of Algorithms conducted by Anna University Chennai.
IV Semester / 04th Semester / Fourth Semester
Department of Computer Science Engineering CSE
CS6402 Design and Analysis of Algorithms
Nov Dec 2016 Important Questions
(Regulation 2013)
CS6402 Design and Analysis of Algorithms - All Important 16 Marks Questions
1. (i) Describe fundamentals of algorithmic problem solving. (10)
(ii) Describe the most important problem types are used to illustrate different algorithm design techniques and methods of algorithm analysis? (6)
2. Show the following equalities are correct.
i. 5n^2 – 6n= Ө (n^2) (4)
ii. n!= O(n^n) (4)
iii. n^3 + 106 ^ = Ө (n^3) (4)
iv. 2n^2 x 2^n + nlogn = Ө (n^2 x 2^n)
3. (i) Prove that for any two functions f (n) and g(n) , we have f (n) = θ (g(n)) if and only (n) = O (g(n)) and f (n) = Ω(g(n)) . (8)
(ii) Classify the various asymptotic notations. (8)
4. If you have to solve the searching problem for a list of n numbers, how can you take advantage of the fact that the list is known to be sorted?
Give separate answer for
(i) Lists represented as arrays.
(ii) Lists represented as linked lists.
Compare the time complexities involved in the analysis of both the algorithms.
5. Explain the recursive algorithm for computing Fibonacci numbers and analyze the same.
6. (i) Explain the Closest pair and convex hull problem in detail. (10)
(ii) Explain the concepts of Brute force string matching. (6)
7. (i) Write down the algorithm to construct a convex hull based on divide and conquer strategy. (8)
(ii) Find the optimal solution to the fractional knapsack problem with the given data: (8)
ITEM WEIGHT BENEFIT
A 2 60
B 3 75
C 4 90
8. (i) Solve the following using Brute – Force algorithm: (10)
Find whether the given string follow the specified pattern and return 0 or 1 accordingly.
Examples:
(1) Pattern: “abba” , input: “redblueredblue” should return 1
(2) Pattern: “aaaa” , input: “asdasdasdasd” should return 1
(3) Pattern: “aabb” , input: “xyzabcxyzabc” should return 0
(ii) Explain the convex hull problem and the solution involved behind it. (6)
9. (i) Write an algorithm to perform binary search on a sorted list of elements. (8)
(ii) Analyze the binary search algorithm for the best, average and worst case (8)
10. Design the knapsack problem with suitable example.
11. Explain Warshall’s and Floyd’s algorithm with suitable examples.
12. (i) Write and analyze the Prim’s Algorithm. (6)
(ii) Consider the following weighted graph. (10)
Give the list of edges in the MST in the order that Prim’s Algorithm inserts them. Start Prim’s Algorithm from vertex A.
13. (i) Let A= { l/119, m/96, c/247, g/283,h/72, f/77, k/92, j/19} be the letters and its frequency of distribution in a text file. Compute a suitable Huffman coding to compress the data effectively. (8)
(ii) Write an algorithm to construct the optimal Binary Search Tree given the roots r(I,j), 0<=i<=j<=n. Also prove that this could be performed in time O(n). (8)
14. Discuss the algorithm to solve all pairs shortest paths problem.
15. Describe single source shortest path algorithm with suitable examples.
16. Explain the Simplex method with suitable examples.
17. (i) Maximize P = 2x+3y+z (8)
Subject to x+y+z<=40
2x+y-z>=10
-y+z>=10
x>=0, y>=0, z>=0
(ii) Write down the optimality condition and algorithmic implementation for finding Maugmenting
paths in bipartite graphs. (8)
18. (i) Explain and solve the problem using maximum flow problem. (12)
(ii) List out the procedures needed to solve the Maximum flow problem by using matrix method. (4)
19. (i) Briefly describe on the stable marriage problem (6)
(ii) How do you compute maximum flow for the following graph using Ford Fulkerson method? (10)
20. (i) Discuss maximum matching bipartite graph algorithm. (8)
(ii) Find the maximal matching for the following graph: (8)
A→{1,2,4}, B→{1},C→{2,3},D→{4,5},E→{3}.
21. (i) Using an example prove that, satisfiability of boolean formula in 3- conjuctive normal form is NP-complete. (12)
(ii) State the relationship among the complexity class algorithms with the help of neat diagrams (4)
22. (i) Create an algorithm to determine Hamiltonian cycle in a given graph Using back tracking. (12)
(ii) For the given graph, determine the Hamiltonian cycle.
23. (i) Show that the Hamiltonian path problem reduces to the Hamiltonian circuit Problem and vice versa. (10)
(ii) What is an Approximation Algorithm? Give Example. (6)
24. (i) The knight is placed on the first block of the empty board and, moving according to the rules of chess, must visit each square exactly once. Solve the above problem using backtracking procedure. (10)
(ii) Implement an algorithm for Knapsack problem using NP-Hard approach. (6)
25. Using branch and bound, describe how to find the optimal solution to a knapsack problem for the knapsack instance n = 8, m = 110, (p1, p2. ... p7) = (11, 21, 31, 33, 43, 53, 55, 65) and (w1, w2,...,w7) = (1, 11, 21, 33, 43, 53, 55, 56).
IUQP wishes you to get success in the examination of CS6402 Design and Analysis of Algorithms conducted by Anna University Chennai.
0 comments:
Pen down your valuable important comments below