Andhra University 2005 B.Tech Information Technology DESIGN AND ANALYSIS OF ALGORITHMS - Question Paper

MODEL PAPER

B. Tech (IT) Degree exam

Third Year - 2nd Semester

DESIGN AND ANALYSIS OF ALGORITHMS

Time: three hrs
Max Marks: 70

First ques. is Compulsory

ans any 4 from the remaining ques.

All ques. carry equal marks

ans all parts of any ques. at 1 place

1. a) What is the time complexity of an algorithm
b) What is the smallest and largest numbers of digits the product of 2 decimal ndigit numbers can have?
c) provide an example of an AVL tree.
d) describe the class P
e) State Travelling Salesman issue
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? discuss the terms: avg. and worst case complexities of an algorithm

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

3. a) define 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) define the Breadth 1st Search algorithm of a provided graph and discuss with an example.

b) Apply the DFS-based algorithm to solve the topological sorting issue for the subsequent 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) define the Floyd’s algorithm for the all pairs shortest paths issue

b) Design a ?(n2) algorithm for finding an optimal binary search tree

7. a) define the Kruskal's algorithm for finding the minimum spanning of a provided graph

b) Construct a Huffman code for the subsequent data:

Character A B C D -
Probability 0.4 0.1 0.2 0.15 0.15

8. a) What is backtracking? discuss it using the n-queens issue.

b) What is NP- completeness? discuss

Earning:   Approval pending.