DESIGN AND ANALYSIS OF ALGORITHMS JNTU previous years question papers

DESIGN AND ANALYSIS OF ALGORITHMS JNTU previous years question papers


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) Suppose a binary tree has leaves l1l2.......lm at depths d1, d2....dm respectively prove that
m
P
i=1
2-di 1 and determine when the equality is true.
(b) Write and explain the control abstraction algorithm of divide and conquer.
[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) Design 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) 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) 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) 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 about cook’s theorem.
(b) Explain the strategy to prove that a problem is NP hard.

FEEL USEFUL PLEASE GIVE +1