R5220502 Design And Analysis Of Algorithms

1

Code No: R5220502

II B.Tech. II Semester (R05) Supplementary Examinations, April/May 2009 DESIGN AND ANALYSIS OF ALGORITHMS (Computer Science & Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks ????? 1. (a) Consider a polynomial in n of the form m P f (n) = ai ni . = am nm + am−1 nm−1 + ..... + a2 n2 + a1 n + a0 where am > 0 then f (n) = Ω (nm ) i=0

(b) Differentiate between profilling and debugging.

[10+6]

2. (a) Derive a time complexity of Quicksort in average case. (b) Explain the divide and conquer method with an example.

[8+8]

3. (a) What is spanning tree? Explain the prim’s algorithm with an example. (b) Explain the terms Feasible solution, optimal solution and objective function. [10+6] 4. (a) Using dynamic programming method, find the maximum no.of operation possible for the following chain matrix multiplication and also the sequence of multiplications that will require this maximum no. of operations A(20,30) * B(30,5) * C(5,12),* D(12,5) (b) Define merging and purging rules in o/1 Knapsack problem.

[10+6]

5. (a) What is articulation point. Write the pseudocode for the articulation point. (b) Show that DFS visits all vertices in G reachable from v.

[8+8]

6. (a) Write a recursive backtracking algorithm for sum of subsets problem. (b) Draw the search tree to color the graph with the three colors: red, blue, green. [8+8] 7. (a) What is Bounding? Explain how these bound are useful in Branch and Bound methods. (b) Describe the TSP in Branch and Bound.

[8+8]

8. (a) Explain about cook’s theorem. (b) Explain the strategy to prove that a problem is NP hard. ?????

[8+8]

2

Code No: R5220502

II B.Tech. II Semester (R05) Supplementary Examinations, April/May 2009 DESIGN AND ANALYSIS OF ALGORITHMS (Computer Science & Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks ????? 1. (a) Explain the asymptotic notations used in algorithm analysis. (b) Prove that f(n)=0(h(n)) where f(n)=0(g(n)) and g(n)=0(h(n)).

[10+6]

2. (a) Design a recursive linear time algorithm that tests whether a binary tree satisfies the search tree order property at every node. (b) Derive the time complexity of strassen’s matrix multiplication.

[8+8]

3. (a) What is spanning tree? Explain the prim’s algorithm with an example. (b) Explain the terms Feasible solution, optimal solution and objective function. [10+6] 4. (a) Solve the following 0/1 Knapsack problem using dynamic programming m=6, n=3, (w1 , w2 , w3 )=(2,3,3), (p1 , p2 , p3 )=(1,2,4) (b) Write an algorithm of all pairs shortest path problem.

[8+8]

5. (a) Find a necessary and sufficient condition for the root of a depth first search for a connected graph to be an articulation point. Prove it. (b) Show that the inorder and postorder sequences of a binary tree uniquely define the binary tree. [8+8] 6. (a) Let w = {20, 18, 15, 12, 10, 7, 5} and m=35. Find all possible subsets of w that sum to m. Draw the portion of the state space tree that is generated. (b) Describe the applications of m-coloring.

[10+6]

7. (a) Explain the general method of Branch and Bound. (b) Explain the principles of LIFO Branch and Bound.

[8+8]

8. (a) Explain the Clique problem and write the algorithm for the same. (b) Differentiate between NP-complete and NP-Hard. ?????

[10+6]

3

Code No: R5220502

II B.Tech. II Semester (R05) Supplementary Examinations, April/May 2009 DESIGN AND ANALYSIS OF ALGORITHMS (Computer Science & Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks ????? 1. (a) Write the non-recursive algorithm for finding the fibonacci sequence and derive its time complexity. (b) Show that f(n) = 4n2 −64n + 288 =Ω (n)2 .

[10+6]

2. (a) Write and explain the control abstraction for Divide and conquer. (b) Suggest refinements to mergesort to make it in-place.

[8+8]

3. (a) Write a greedy algorithm to the Job sequencing with deadlines. (b) Prove that the edge with the smallest weight will be part of every minimum spanning tree. [8+8] 4. (a) Explain the matrix chain multiplication with an example. (b) Find the shortest tour of a TSP for the following graph (figure 1)using dynamic programming. [8+8]

Figure 1: 5. (a) Write a pseudocode for finding the strongly connected components of directed graph. Also analyze its time complexity. (b) Explain the Inorder traversal of a tree with an example.

[8+8]

6. (a) Write an algorithm of finding all m-colorings of a graph. (b) Describe the 4-queens problem using backtracking.

[8+8]

7. (a) Explain the method of reduction to solve TSP problem using Branch and Bound. (b) Explain the principles of FIFO Branch and Bound.

[8+8]

8. (a) Explain the classes of NP-hard and NP-complete. (b) Describe clique decision problem and write the algorithm for the same. ?????

[8+8]

4

Code No: R5220502

II B.Tech. II Semester (R05) Supplementary Examinations, April/May 2009 DESIGN AND ANALYSIS OF ALGORITHMS (Computer Science & Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks ????? 1. (a) Write the non-recursive algorithm for finding the fibonacci sequence and derive its time complexity. (b) Show that f(n) = 4n2 −64n + 288 =Ω (n)2 .

[10+6]

2. (a) Write a search algorithm in a binary search tree. (b) List some of the advantages and disadvantages of the partition algorithm. [10+6] 3. Write and Explain the Kruskal’s algorithm for finding the minimum cost spanning tree. What is its time complexity. [16] 4. (a) Find one problem for which the principle of optimality does not hold. Explain why the principle does not hold. (b) Find the shortest path between all pairs of nodes in the following graph. (Figure 1)

[8+8]

Figure 1: 5. (a) A directed graph G=(V,E) is singly connected if u → v implies that there is atmost one simple path from u to v for all vertices u, v ∈ V. Give an efficient algorithm to determine whether or not a directed graph is singly connected. (b) Differentiate between BFS and DFS.

[10+6]

6. Write the control abstraction of backtracking write backtracking algorithm for 8-queen problem. [16] 7. (a) Explain the method of reduction to solve TSP problem using Branch and Bound. (b) Explain the principles of FIFO Branch and Bound.

[8+8]

8. (a) Explain the classes of NP-hard and NP-complete. (b) Describe clique decision problem and write the algorithm for the same. ?????

[8+8]