**Model papers of Andhra University **

**B Tech Computer Science & Engineering **

** Design and Analysis of Algorithms**

**(CSE) Degree Examination**

**Third Year – Second Semester**

Effective from the admitted batch of 2004-2005

Time: 3 hrs

Max Marks: 70

First Question is Compulsory

Answer any four from the remaining questions

All Questions carry equal marks

Answer all parts of any question at one place

1. a) What is the time complexity of an algorithm

b) What is the smallest and largest numbers of digits the product of two decimal ndigit numbers can have?

c) Give an example of an AVL tree.

d) Define the class P

e) State Travelling Salesman Problem

f) What is the transitive closure of a digraph?

g) What is a convex hull?

2. a) How do we judge the efficiency of an algorithm? Explain the terms: Average and worst case complexities of an algorithm

b) Design a recursive algorithm for computing 2^{n} using the formula 2^{n} = 2^{n-1} + 2^{n-1}. What is it’s computing time?

3. a) Describe the quick sort algorithm using the divide-and-conquer strategy.

b) Apply quick sort to sort the list E, X, A, M, P, L, E in alphabetic order. Draw the tree of the recursive calls made.

4. a) Describe the Breadth First Search algorithm of a given graph and explain with an example.

b) Apply the DFS-based algorithm to solve the topological sorting problem for the following digraph.

—–DIAGRAM—–

5. a) Write an algorithm for Heap Sort algorithm and illustrate it with an example.

b) Write an algorithm for finding the largest key in a B-tree.

6. a) Describe the Floyd’s algorithm for the all pairs shortest paths problem

b) Design a θ(n^{2}) algorithm for finding an optimal binary search tree

7. a) Describe the Kruskal’s algorithm for finding the minimum spanning of a given graph

b) Construct a Huffman code for the following data:

Character | A | B | C | D | – |

Probability | 0.4 | 0.1 | 0.2 | 0.15 | 0.15 |

8. a) What is backtracking? Explain it using the n-queens problem.

b) What is NP- completeness? Explain