R05321904-design-and-analysis-of-algorithms

Set No. 1

Code No: R05321904

III B.Tech II Semester Supplimentary Examinations, Aug/Sep 2008 DESIGN AND ANALYSIS OF ALGORITHMS (Electronics & Computer 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) Prove that if the weights on the edges of a connected undirected graph are distinct then there is a unique minimum spanning tree. (b) Explain the general characteristics of Greedy method.

[8+8]

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) Explain the properties of strongly connected components. (b) Write a non-recursive algorithm of In-order traversal of a tree and also analyze its time complexity. [6+10] 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) 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 Clique 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: R05321904

III B.Tech II Semester Supplimentary Examinations, Aug/Sep 2008 DESIGN AND ANALYSIS OF ALGORITHMS (Electronics & Computer Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks ⋆⋆⋆⋆⋆

1. (a) Develop a probabilistic algorithm to find the value of the integral

R2 √ 0

(b) Differentiate between priori analysis and posteriori analysis.

4 − x2 dx [10+6]

2. (a) List some of the relative advantages and disadvantages of the partition algorithm (b) Write the Quicksort algorithm? Analize the time complexity in worst case. [6+10] 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) 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 4b) [8+8]

Figure 4b 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) Draw the state space tree for m coloring when n=3 and m=3 (b) Write a recursive backtracking algorithm.

[8+8]

7. (a) Write an algorithm to solve the Knapsack problem with the Branch and Bound (b) Differentiate between Dynamic Knapsack and Branch and Bound Knapsack problem. [10+6] 1 of 2

Set No. 2

Code No: R05321904

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

2 of 2

[10+6]

Set No. 3

Code No: R05321904

III B.Tech II Semester Supplimentary Examinations, Aug/Sep 2008 DESIGN AND ANALYSIS OF ALGORITHMS (Electronics & Computer 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) 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. Determine the cost and structure of an optimal Binary search tree for a set of n=5keys with the following probabilities. p1 = p2 = 0.125, p3 = p4 = 0.0625, P5 = 0.1875 q0 = 0, q1 = 0.1875, q2 = q3 = q4 = q5 = 0.0625 The keys are a1 < a2 < a3 < a4 < a5 . [16] 5. (a) Explain game tree with an example. (b) Prove or disprove an undirected graph G=(V,E) is biconnected if and only if for each pair of distinct vertices u and v there are two distinct paths from u to v that have no vertex in common except u and v. [8+8] 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 to solve the Knapsack problem with the Branch and Bound (b) Differentiate between Dynamic Knapsack and Branch and Bound Knapsack problem. [10+6] 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

Set No. 4

Code No: R05321904

III B.Tech II Semester Supplimentary Examinations, Aug/Sep 2008 DESIGN AND ANALYSIS OF ALGORITHMS (Electronics & Computer Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks ⋆⋆⋆⋆⋆

1. (a) Develop a probabilistic algorithm to find the value of the integral

R2 √ 0

(b) Differentiate between priori analysis and posteriori analysis.

4 − x2 dx [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) Show that the greedy algorithm to minimize the mean completion time for multiprocessor Job scheduling. (b) Write an algorithm of Greedy Knapsack and Also analyze its time complexity. [8+8] 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. Write an algorithm of Biconnected components and also analyze its time complexity. [16] 6. Write the control abstraction of backtracking write backtracking algorithm for 8queen problem. [16] 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 satisfiability problem and write the algorithm for the same. (b) Differentiate between NP-complete and NP-Hard. ⋆⋆⋆⋆⋆

1 of 1

[10+6]