R05220502-design-and-analysis-of-algorithms

Set No. 1

Code No: R05220502

II B.Tech Supplimentary Examinations, Aug/Sep 2008 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) Show that f(n)+g(n)=O (n2 ) where f (n) = 3n2 − n + 4 and g(n)=nlogn+5 (b) Explain how time complexity of an algorithm is computed.

[8+8]

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 Greedy algorithm to generate shortest path. (b) If p1 /w1 ≥ p2 /w2 ......... ≥ pn /wn prove that knapsack generates an optimal solution to the given instance of the knapsack problem. [8+8] 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) 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. (a) Draw and explain the portion of the tree for 4-queens problem that is generated during backtracking. (b) Explain the applications of Backtracking.

[10+6]

7. (a) Write an algorithm of LCBB to find the minimum cost answer node. (b) Describe explicit constraints and implicit constraints.

[10+6]

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

1 of 1

[10+6]

Set No. 2

Code No: R05220502

II B.Tech Supplimentary Examinations, Aug/Sep 2008 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) Define time complexity. Describe different notations used to represent there complexities. (b) Derive the function f(n)= 12n2 +6n is 0(n3 ) and w(n).

[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. Show that prim’s algorithm can like Kruskal’s algorithm be implemented using heaps. Show that it then takes a time in θ(alogn). [16] 4. (a) Solve the matrix  0 2  6 0   ∞ ∞   ∞ ∞ 3 ∞

all-pairs shortest path problem for the digraph with the weight  ∞ 1 8 3 2 ∞   0 4 ∞   2 0 3  ∞ ∞ 0

(b) What is Travelling sales person problem and what are its applications. [10+6] 5. (a) Explain the BFS algorithm with an example. (b) The Preorder and Postorder sequences of a binary tree do not uniquely define the binary tree. Justify the answer. [8+8] 6. (a) Let w = {5, 7, 10, 12, 15, 18, 20} 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) Compare and Contrast Brute force approach and Backtracking.

[10+6]

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 Clique problem and write the algorithm for the same. (b) Differentiate between NP-complete and NP-Hard. ⋆⋆⋆⋆⋆

1 of 1

[10+6]

Set No. 3

Code No: R05220502

II B.Tech Supplimentary Examinations, Aug/Sep 2008 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 n3 logn is w(n3 ).

[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) What is spanning tree? What is the importance of finding minimal spanning tree. (b) Find the shortest path for the given graph ( Figure 3b) by using single source shortest path. [6+10]

Figure 3b 4. Write a pseudocode of the dynamic programming algorithm for solving Optimal Binary search tree and determine its time and space efficiencies. [16] 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 = {15, 7, 20, 5, 18, 10, 12} 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) Write the control abstraction of backtracking.

[10+6]

7. (a) Describe problem state, solution state and answer state with an example. (b) Explain the general method of Branch and Bound.

[8+8]

8. (a) Explain the satisfiability problem and write the algorithm for the same. 1 of 2

Set No. 3

Code No: R05220502 (b) Differentiate between NP-complete and NP-Hard. ⋆⋆⋆⋆⋆

2 of 2

[10+6]

Set No. 4

Code No: R05220502

II B.Tech Supplimentary Examinations, Aug/Sep 2008 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) Define omega notation. Explain the terms involved in it. Give an example. (b) Show that f1 (n)×f2 (n) = 0(g1 (n)×g2 (n) wheref1 (n) = 0(g1 (n) and f2 (n) = 0(g2 (n)). [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) How many comparisons of edge weights will be done by the minimum spanning tree algorithm, in total, if the input is a complete undirected graph with n vertices and vi is the start vertex. (b) Deisgn a linear-time algorithm for solving the single source shortest path algorithm for directed a cyclic graphs represented by their adjacency linked lists. [6+10] 4. (a) Explain matrix chain multiplication with an example. (b) Solve the following 0/1 Knapsack problem using dynamic programming P=(11,21,31,33), W=(2,11,22,15), C=40, n=4. [8+8] 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) Apply backtracking to solve the 3-coloring problem for the graph of fig. (b) Write an algorithm of n-queens problem.

[8+8]

7. (a) Explain live node, E-node and dead node with an example. (b) Explain the method of reduction to solve TSP problem using 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] ⋆⋆⋆⋆⋆

1 of 1