MODEL PAPER

B. Tech (CSE) Degree Examination

Third Year - Second Semester

DESIGN AND ANALYSIS OF ALGORITHMS

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ⁿ using the formula 2ⁿ = 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²) 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:

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

b) What is NP- completeness? Explain